Here are the earliest forms of "colder than a witch's kiss," "colder than a witch's teat," and "colder than a witch's tit" that a Google Books search turns up.
The first found instance of (approximately) "colder than a witch's kiss" is in William Lindsay Gresham, Limbo Tower (1949), page 13 [snippet]:
Frank Vitiello's voice complained, "Hey, quit it. Come on, sister, gimme them covers. This joint's as cold as a witch's kiss."
The first found instance of "colder than a witch's teat" is in Maurine Whipple, This Is the Place: Utah (1945), pages 176–177 [snippet]:
It is a land that has even its own language. That good-looking housewife over there "bore her testimony" last Sunday. Because your friend looks unusually well-fed and paunchy, you tell him he's "grown a bishop"; this because in the hungry early days bishops controlled the tithing, which was always paid in kind. Maybe your neighbor "went to temple" last week and put on his "long-handled underwear." In any case, if he "takes the water" on Sundays or when it isn't his "turn," you warn him he'll "get his church cut off." If he sees you spreading manure on your lawn, he may rally you about "spreading the gospel." That cranky brother has a "smile as sour as the ripple on a swill barrel." The weather is "colder than a witch's teat." The dunce in school was "born on washday." One with a sudden inspiration has a "wild-hair." That "ham-scrammin' " girl you flatter "takes it in like cream from the cat-jar." Do you want to damn a stingy man? You tell him he has in his veins "the blood of a profit."
Another early (approximate) occurrence is in J.D. Salinger, The Catcher in the Rye (1951), page 4 [snippet]:
Anyway, it was December and all, and it was cold as a witch's teat, especially on top of that stupid hill. I only had on my reversible and no gloves or anything. The week before that, somebody'd stolen my camel's-hair coat right out of my room, with the fur-lined gloves right in the pocket.
The first found instance of "colder than a witch's tit" is in Literary America vol. 2, issue 2 (1935), page 139 [snippet]:
"Where's Millar?" I asked, knowing.
It was a cue for a duet. They must have rehearsed it.
"Hung, Barr, hung. With that Chink belt you're holding there. Dead for over a month. Colder than a witch's tit."
This last is a brief snippet from a story of unknown length, but I confirmed elsewhere that volume 2 issues of Literary America were published in 1935.
The next-oldest instance is in Jerome Weidman, I'll Never Go There Any More (1941), page 58 [snippet]:
"It's the summer. You have to expect heat in New York in the summer no matter where you are. But wait till the wintertime comes. It'll be as cold as a witch's tit."
"The wintertime? You didn't sublet this for the full year, did you?"
"Certainly I did. You don't think I was going to let a bargain like this slip by. I sewed it up for the whole year. Why?"
Google Books also finds a reference to the similar "dry as a witch's tit" in an unidentified snippet in Tomorrow, vol. 10 (1950), page 15 [snippet]:
"My God-damn lighter's gone dry as a witch's tit," the boy said, and Janos could hear the rasp of the lighter's stone in his hand. "I got to get me to a P.X. and get me some lighter fluid. I got to find me an American shoe-repair and get some soles put on my shoes. I walked through 'em today, but I got the schnapps," he said. When he sat up in the hay, his head and his neck and his shoulders in the G.I. sweater showed dark against the starry square of night.
However, Robert L. Chapman & Barbara Ann Kipfer, Dictionary of American Slang, Third Edition (1995), argues that these allied expressions are offshoots of an older tradition:
cold as (or colder than) hell adj phr (Variations: charity or Kelsey's ass or a welldigger's ass or a witch's tit may replace hell) charity form by 1835, witch's tit by 1932, welldigger's ass by 1940's. Kelsey was often identified as the welldigger Very cold In Chicago that December 1955, it was colder than a well-digger's ass in the Klondike—Earl Thompson/ It's as cold as a witch's tit outside—Van Wyck Mason
Supposedly, the Van Wyck Mason quotation comes from a 1932 mystery novel titled Spider House, though I haven't been able to confirm that claim directly.
In any event, Google Books finds instances of "cold as charity" going back to James Howell, Paroimiographia: Proverbs, or, Old Sayed Sawes & Adages (1659), page 16, which lists "As cold as Charity" as an English proverb.
To my surprise, the first Google Books matches for "cold as hell" are much more recent than those for "cold as charity." The earliest occurrence of "cold as hell" that I've found in Google Books is in P.T. Barnum, Struggles and Triumphs; Or Forty Years' Recollections of P.T. Barnum (1873), page 246:
Early one morning, several of these youths came upon deck, and, meeting the Doctor there, one of them exclaimed: "It is cold as hell this morning, ain't it, Doctor?"
"I am unable to state the exact height of the thermometer in that locality," said he gravely; "but I am afraid you will know all about it some time, if you are not careful."