Of American-English origin, the phrase until hell freezes over, and its variants, mean: for an extremely long time or forever.
—Synonym: until Nelson gets his eye back.

The earliest occurrences of the phrase until hell freezes over and variants that I have found are as follows, in chronological order:

1-: From the Evangelical Magazine and Gospel Advocate (Utica, New York) of Saturday 4^th February 1832:

ORTHODOX PIETY AND MANNERS.

Week before last, we received through the Post Office, a number of the “National Preacher,” a thoroughgoing Presbyterian paper; and on the margin of one of its leaves was written this religious, polite, and complaisant message: “Read this paper, old Skinner, you dam’d old sinner”! And last week we received a copy the Magazine and Advocate, returned from Baldwinsville Post Office, in Onondaga county, on the margin of which was written a message altogether as polite as the above, and breathing equally as much Orthodox zeal and piety. This was the message written: “Mr.” (naming the subscriber to whom the paper was addressed,) “lives at Syracuse—you can send it there—for God’s sake don’t you send it here any more—don’t you send this dam thing here”! This week we received another paper returned from the same office (which had been mailed before the other number was returned) on the margin of which is written, “Stop this paper or send it to Syracuse, where — lives. Baldwinsville, Onon. co. N.Y. I shall send it back until hell freezes over, but what I will stop it. I don’t want to pay postage on the d— thing.”
These two cases are fair samples of the spirit that actuates some of our opposers. Must not the more sober and rational part of them blush at such folly, weakness, and wickedness? We should think so, if they have any shame. If not, we pity them—we neither envy, nor feel angry at them—they are beneath our indignation, and almost beneath contempt. The last instance named was undoubtedly the act of a pious Post Master, or one of his new-born clerks. We will merely ask him, if this was the business for which he was appointed Post Master? if he thinks this manner of discharging the responsible duties of his office, will meet the approbation of the General P. O. Department? and lastly, is this the spirit of his religion?—What would be our destiny, and the destiny of our country, if such men were the framers and executioners of our laws?
S.

2-: From a letter dated Thursday 15^th February 1849, by a person signing themself ‘A. T—’, published in the Wisconsin Tribune (Mineral Point, Wisconsin) of Friday 16^th March 1849:

“These men of course would pray with their lips, and blasfeme in their harts, and though they deceive men, and get fat on their substance, God has set his mark on them, and if there was a hell for no others, if all others can be forgiven, still the hipocrite shall roast till hell freezes over, and then he shall freeze till Greenland thaws out.”

3-: From On Wisdom and Patience, published in New Patent Sermons, Machine Poetry, and Lectures on Animals, &c. (New York: Frederic A. Brady, 1859), by Dow, Junior, pseudonym of the U.S. humorist Elbridge Gerry Paige (1816-1859):

Patience! yes, you can do a good deal if you only have patience. You can carry water in a sieve, as an old fogy uncle once told his nephew—if you wait till it freezes. And so, my brethren, you can all get safely to heaven at last—it [sic] you live long enough, and have the patience to wait till hell freezes over. So mote it be!

4-: From the New Orleans Daily Crescent (New Orleans, Louisiana) of Thursday 26^th January 1860:

Local Intelligence.

The Poor Old Man is Gone at Last.—Who is there in this town who never knew, or saw, or heard of old Counsellor Randolph—Alexander A. Randolph—“Randolph of Roanoke,” as many called him, or “Randolph of London,” as the coffeehouse wags addressed him when they wished to hear him exercise his talent at abuse and ventilate his patriotism as an American? Very few, we imagine. His long practice at the bar (in both the courts and the coffeehouses), has, we are sure, made him well known to those at least who inhabit and frequent such places.
[…]
A good thing is told of the Commodore. A Mexican trading vessel had come on business to this port. Randolph came in with his cruiser on a friendly visit. Discovering the Mexican, he cleared out, and waited near the Passes to make a prize of her. After a while the Mexican came out, and Randolph and his cruiser started in pursuit. But at the same time an United States revenue cutter started in pursuit of Randolph, the chase being on ground, or on water, within United States limits. The Commodore dropped the Mexican, and crowded sail to get away from the cutter. Some of his men talked mutinously, and wanted to heave to and give the cutter a fight. The Commodore stamped his foot and shouted furiously: “Never! we’ll run till hell freezes! And, as long as I command, no shot shall ever be fired at the stars and stripes!”

5-: From the Evening Star (Washington, District of Columbia) of Saturday 28^th January 1860:

Going to Stick to Sherman.—Hon. Tom Corwin said he would continue to vote for Sherman until Gabriel’s last trump should sound. According to the Washington correspondent of the Boston Bee, there is another member who says that “they are going to vote for him, if necessary, until hell freezes from shore to shore.” It will be seen Monday.

6-: From the account of the Democratic State Convention, published in the Richmond Daily Whig (Richmond, Virginia) of Monday 20^th February 1860:

The disorder now reached its highest pitch, and if the simile of piling “Pelion upon Ossa” served to convey any idea of the intensity of the din previously prevailing it would now be fair and truthful to say that Ossa had dwindled to a wart. Let the reader imagine a thousand packs of hounds in full bay—all yelping at once—and he will have a faint conception of the discordant uproar which was kept up for several minutes. Mr. Cooke, of Wythe, had taken a position on the stand to speak, and about fifty members were addressing the Chair in various parts of the Hall.
Mr. Cooke. By G—d, gentlemen, I’ll stand here till hell freezes over. (Yells, laughter, and calls for Cooke.) If you will hear me but two minutes, I can settle the whole matter.