How did "stone-cold" come to mean completely?

Solution 1:

Not surprisingly, the earliest instances of "stone cold" that a Google Books search turns up use the wording to signify "as cold as stone," not "completely." For example, from Roger L'Estrange, Fables of Æsop and Other Eminent Mythologists: With Morals and Reflexions, second edition (1694):

His Wife was given over, and himself waiting in the next Room, with the Rage and Impatience of a Mad-man, for fear of Ill News; when at last, in comes one of the Nurses to him, with the Dismal Tydings, that my Poor Lady was Dead, and had been now Stone Cold for at least a Quarter of an Hour.

From Mrs. Gore, Mrs. Armytage, Or Female Domination (1836):

Yet natural are selfish predilections:/ Like snakes they writhe about the heart's affections,/ And sometimes, too, infuse a poisonous spirit;/ Producing, as by naturalists I'm told,/ Torpid insensibility,—stone-cold/ To every human brother's merit.

Mrs. Gore attributes this quotation to "Dr. [John] Wolcot," who wrote under the pseudonym Peter Pindar; but Wolcot's original wording, in "To My Ass, Peter" (1792), is "Torpid insensibility, so cold/ To ev'ry Brother's rising merit." So it appears that "stone cold" is Mrs. Gore's invention.

And from Thomas Halliburton, The Clockmaker: or, The Sayings and Doings of Sam Slick, of Slickville (1839):

I never see a clever lookin gall in danger of that, I don't long to whisper in her ear, you dear little critter, you, take care, you have too many irons in the fire, some on' em will get stone cold, and tother ones will get burnt so, they'll never be no good in natur.

The earliest instance I could find of "stone-cold" as a compound modifier with the sense "absolute," "complete," "unchangeable," or "incontrovertible" appears in "An Elixir of Life" in the Brisbane Courier (October 16, 1909):

Idleness works mental and physical destruction, and the wider one's interests, the more actively pursuits are followed, the more one undertakes, the better for one's health, mind, and morals. This is not mere copy-book sentiment; it is what our American friends call a "stone-cold fact." You may diet, you may spend a fortune in "-cures," you may obey every new rule of health laid down, but you will neither keep well nor amiable nor agreeable, nor will you achieve exceptional length of days, unless your mental machinery is in constant use.

And from an advertisement for Sims Book Store in the [Orangeburg, South Carolina] Times and Democrat (December 17, 1910):

It's a stone cold fact that we have the largest and most complete line of Blank Books in the city.

This Americanism seems very similar in sense to the phrase "cold, hard fact[s]," which may have inspired it. Instances of "cold hard fact[s]" go back at least to 1867. From a letter to the editor of the [Plymouth, Indiana] Marshall County Republican (August 1, 1867):

This phase of crime has its statistics, and it is somewhat startling to meet the cold, hard facts that in all our cities the number of women who follow a life of open prostitution, together with kept mistresses and wives who meet male friends by appointment at other places than their own homes, must be computed by thousands.

From "The Prescription," in the [Charlestown, West Virginia] Spirit of Jefferson (September 23, 1873):

And then he placed the cold, hard facts before him, from the time she came as a bride, beautiful and accomplished, to the village, up to the date of her present illness, in which domestic cares only had haunted her feverish dreams.

And from "Political Notes" in the New-York Tribune (April 9, 1877):

Ex-Congressman Watterson doesn't waste any time in trying to extract warmth out of an icicle but acknowledges the cold hard fact at once.

Conclusion

It seems quite possible that "stone-cold" in the relevant sense arose as part of the longer phrase "stone-cold fact[s]," which itself may have arisen as alternative form of "cold, hard fact[s]." Once English speakers had adopted that meaning of "stone-cold," the modifier migrated to other settings, such as "stone-cold believer," "stone-cold certainty," "stone-cold sober," and "stone-cold perfect."

UPDATE (11/15/2016): 'Stone-' as a generic marker for 'completely'

Alan Carmack's very useful comment (below) about the long-established terms "stone blind" and "stone still" (to which we might add "stone dead," which Richard Hooker uses in A Learned Discourse on Justification [1612]) led me to look into when stone in the sense of "completely" might have arisen outside the context of "stone cold."

The case of "stone blind" is particularly intriguing because, in the first place, we can find examples of it going at least as far back as Thomas Dekker, The Belman of London (1609):

Many other practises there are in bowling tending to cozenage, but ye greatest and grosest is Booty : in which ye deceipt is so open and palpable, yt I have séene men stone-blind offer to lay Betts franckly, although they could sée a bowle no more than a post, only by hearing who played, and how the old Grypes had made their layes.

Here "stone-blind" unmistakably means "blind as a stone"; but dos it also mean "completely blind"? A hint that it does comes from The Merchant of Venice (ca. 1596–1599), in which Shakespeare offers this bit of dialogue:

Old Gobbo. Master young man, you, I pray you, which is the way to master Jew's?

Launcelot Gobbo. O heav'ns, this is my true-begotten father, who being more then sand-blind, high-gravel-blind, knows me not; I will try confusions with him.

It is easy (and perhaps accurate) to imagine a continuum of blindness ranging (for humorous effect, in Shakespeare's usage) from sand-blind (which Nathan Bailey, An Universal Etymological English Dictionary [1731] defines as "Purblind or Short-sighted") through high-gravel-blind (not a real thing, presumably) to stone blind (completely blind). If so, stone already had as one of its senses the precise meaning "completely" at least as early as the late 1500s.

Harold Wentworth & Stuart Flexner, Dictionary of American Slang (1960) includes this interesting entry for "stone—" as a prefix word:

stone—. In certain specific formations noun stone is used as an adjective = completely, totally, utterly. Thus the standard stone blind = totally blind, and slang's stone broke, stone dead [meaning totally drunk], and stone rich. Since stone— is always followed by a word which implies totally or completely, it is primarily used for emphasis.

Still, the OP asks not about how stone came to mean "completely" but how "stone-cold" did. And clearly "stone-blind," "stone-still," and "stone-dead" do not mean "completely"—they mean "completely blind" "completely still," and "completely dead." So I think that in a crucial way the question about "stone-cold" invites the narrow focus that my answer originally gave it.

Solution 2:

The idea of a stone used metaphorically to refer to cold, indifferent human feelings is very old an can be found in Shakespeare's works. I think that the idea of "complete, absolute" is a logical extension of the original meaning. Stones are a good example of something that is not subject to change. They are hard and unyielding, an example of an "absolute", whereas most of other things can be changed in some way.

Stone cold:

• Unfeeling, insensible, as in That sad story left her stone cold.

• This analogy was already used by Shakespeare in Henry V (2:3): “Cold as any stone.”

(The American Heritage Idioms Dictionary)

Examples:

• But the stone cold fact is his children still love him, just as much as they love their mother.

From: (Are the Glory Days of Fatherhood Over? Michael Lewis June 19, 2009)

• So there she sat like stone—cold, and silent, and wan, as the effigy she watched.

From: (Harper's New Monthly Magazine, Volume 2, No. 12, May, 1851.)