Christine Ammer, The Facts on File Dictionary of Clichés, second edition (2006) has this entry for the phrase "not until the cows come home":
not until the cows come home Not for a long time. Presumably the time referred to is when cows return to the barn for milking. The term has been around since the late sixteenth century. Beaumont and Fletcher's play The Scornful Lady (1610) stated, "Kiss till the cow come home."
Robert Allen, Allen's Dictionary of English Phrases (2008), who also cites The Scornful Lady, concurs with Ammer as to the original sense of the phrase:
till the cows come home
for ever, indefinitely: from the former practice of leaving cows out at pasture until they were ready for milking. 16th cent
Early usage in England
Here is the quotation from The Scornful Lady with a bit more of the surrounding play for context:
Enter young Loveless, and his Comrades, with Wenches, and two Fidlers.
Young Loveless. Come my brave Man of War, trace out thy darling,/And you my learned Council, sit and turn Boys,/Kiss till the Cow come home, kiss close, kiss close Knaves./My Modern Poet, thou shalt kiss in Couplets./ Enter with Wine. /Strike up you merry Varlets, and leave your peeping, This is no pay for Fidlers.
Like Ammer and Allen, William Carew Hazlitt, English Proverbs and Proverbial Phrase Collected from the Most Authentic Sources (1907) cites the occurrence in The Scornful Lady (albeit with a later publication date, but Hazlitt presents the proverbial phrase itself as including the word kiss:
Kiss till the cow come home
This appears to be introduced proverbially into Fletcher's Scornful Lady, 1616, where Loveless says: "And you, my learned council, set and turn, boys;/Kiss till the cow come home." [Citation omitted.]
However, Hazlitt fails to note that Beaumont and Fletcher used "till the cow come home" in another play—The Captain (circa 1609–1612)—in the context of drinking rather than kissing:
Host. Good night!
Jacomo. Good morrow! Drink till the cow come home, 'tis all paid boys.
George Apperson, The Wordsworth Dictionary of Proverbs (1993), which I believe is a reprint of Apperson's English Proverbs and Proverbial Sayings: A Historical Dictionary (1929) gives an instance of "till the cow come home" from Alexander Cooke, "Pope Joan: A Dialogue Between a Protestant and a Papist" (1625), reprinted in The Harleian Miscellany (1745):
And when he is made one [a priest], and hath gotten a Benefice, he consorts with his Neighbour Priests, who are altogether given to Pleasures ; and then both he, and they, live, not like Christians, but like Epicures; drinking, eating, feasting, and revelling, till the Cow come Home, as the Saying is ; playing at Tables, and at Stool-ball ; and, when they are well crammed and tippled, then they fall by the Ears together, whooping, and yelling, and swearing damnably, by God and all the Saints in Heaven.
and a first occurrence of the modern form "till the cows come home" from Swift, Polite Conversation, Dialogue II (1738):
Miss Notable. I suppose, my lord, you lay longest abed today?
Lord Smart. Miss, if I had said so, I should have told a fib; I warrant you lay abed till the cows came home: but, miss, shall I cut you a little crust, now my hand is in?
Miss Notable. If you please, my lord, a bit of undercrust.
Usage in the United States
In a Google Books search for the phrase, "till the cows come home," the earliest match appears in the context of an extended example of "The Yankee Dialect" in a handbook titled How to Talk (1857):
He [the Yankee] says I guess when he means I think ; uses the word awful in the sense of ugly and very great ; ary for either ; back and forth for back and forward ; blows up his help instead of scolding them ; swaps jack-knives and horses ; is seldom green enough to get into a fix ; generally goes the whole figure, and holds on "till the cows come home ;" but occasionally his enterprises fizzle out, and he is obliged to fork over the dimes and back out, or be smashed up.
By "Yankee," the anonymous author of this handbook seems to mean "New Englander," since he addresses "The New York Dialect" in a separate section.
Other examples soon follow. From a letter dated September 23, 1858, and included in Life and Correspondence of Theodore Parker: Minister of the Twenty-eighth Congregational Society, Boston, volume 2 (1864):
Massachusetts is likely to send a stronger anti-slavery delegation to Congress than ever before. ... Governor Banks would, no doubt, lower the Republican platform, if that operation would help him up. But Massachusetts will oppose any such act, so will the people of the North. If we put up a spooney, we shall lose the battle, lose our honor, and be demoralized. Edward Everett is beating every New England bush for voters to elect him. He may beat till the cows come home, and get little from his labor.
And from Gail Hamilton, "The Pursuit of Knowledge under Difficulties," in Atlantic Monthly (March 1860):
"But do consider, Mr. Geer, the child has got to leave us some time. We can't have her always."
"Why can't we?" exclaimed Mr. Geer, almost fiercely.
"Sure enough! Why can't we? There a'n't nobody besides you and me, I suppose that thinks she's pairk. What's John Herricks and Dan Norris hangin' round for all the time?"
"And they may hang round till the cows come home! Nary hair of Ivy's head shall they touch,—nary one on 'em!"
(I have no idea what pairk means in the above quotation.)
The earliest form of the expression seems to have been "till the cow come home" from the late 1500s or early 1600s, with "till the cows come home" in use by 1738. The references I consulted agreed that the expression refers to cows coming back to the barn from the pasture either in the evening or in the morning, not to cows escaping the confines of a farm and not returning at all. Indeed, Eric Partridge, in his edition of Swift's Polite Conversation says that the original phrase had the sense "till the cow come home for milking."