The earliest instance that I have found is from The Detroit Free Press (Detroit, Michigan) of Friday 9th April 1880, in an article about the Republican National Convention that was to take place in June:
Mr. George C. Gorham¹, ex-Secretary of the Senate, who not long since remarked, with a good deal of vigor, that under the Hayes² administration a Republican in the South had about “as much chance as a snowball in hell,” now supports Grant³.
¹ George Congdon Gorham (1832-1909), Republican politician and newspaper editor; Secretary of the United States Senate from 1868 to 1879
² Rutherford Birchard Hayes (1822-93), 19th president of the United States from 1877 to 1881
³ Ulysses Simpson Grant (1822-85), general and 18th president of the United States from 1869 to 1877
The second-earliest instance that I have found is from the Las Vegas Daily Gazette (Las Vegas, New Mexico) of Thursday 27th March 1884:
There is no more show for the people of New Mexico to have a word to say in reference to the laws that shall be enacted during the next nine days than there is for a snowball in hell.
The phrase was probably well established at the turn of the 1880s, since a variant with the lower regions instead of hell appeared in The Atlanta Constitution (Atlanta, Georgia) of Monday 24th November 1890; in an article about a contested election for representative in Liberty county, this newspaper reported that, on the question of whether Mr. Norman had voted for Mr. Gordon, the attorney for Norman declared:
“It is true that Mr. Norman came to Atlanta instructed to vote for Mr. Norwood, and he did vote so on the call of the roll, but after the roll call was over and he saw that Norwood’s chances were about like a snowball’s chances in the lower regions, he exercised what he considered his right and voted for Gordon as his second choice, and it was his vote that elected Gordon, too.”
The earliest occurrence of the elliptical form that I have found is from The Daily Inter Mountain (Butte, Montana) of Monday 3rd June 1895:
There are two sides to the gambling question—the moral side and the business side, and it is for the authorities to decide what is the best course to pursue. There is no doubt, however, about the wisdom of giving immediate attention to the suppression of sure thing games which it is reported are now in operation in the lower part of the city, and where those inclined to wrestle with the tiger have but a snowball chance for their money.
In the 1880s, a snowball in hell was also used as a term of comparison to denote something that disappears rapidly; the following is from the Rio Grande Republican (Las Cruces, New Mexico) of Saturday 27th January 1883:
On Saturday 3rd November 1883, the same newspaper had the following paragraph:
A snowball in hell will not disappear more quickly than your friend, if you ask him to drink at any other saloon than the Commercial, where John Clark and Charley preside.
Likewise, H. R. Haxton made a character say the following in a story titled A Wyoming Wedding, published in The Omaha Sunday Bee (Omaha, Nebraska) of 6th March 1887:
“That rheumatiz is a pesky thing, ain’t it? A man can’t last no longer than a snowball in hell, ridin’ with that in him.”