Did it exist before The Telephone - has it always been associated with 'sales'?
Here is an example.
As jargon for an unsolicited sales pitch, cold call, was used way before the 1970s. The earliest use I can find is from Volume 100 of The American Magazine in 1925:
. . . I do need insurance.' He signed up forthwith for five thousand dollars. "I suppose you might call that opportunity a 'hunch.' I had no introduction to the man, no personal link of any kind. It was a cold call, and it won.
This snippet is all I can get through Google. If anyone can access this magazine, it would be great to get more context for the quote. The term seems to have been popularized thereafter by salesmen trade publications in the later 1920s.
The phrase itself is most likely older than this. I have two other citations where the meaning of its use is not exactly clear to me. The first is from a collection of field notes taken by British entomolgist Augustus Radcliffe Grote and published in 1877:
I also had visitors still higher up in the scale of nature. Some Indians, from the Reservation near by, paid me a cold call. These did not come to 'sugar,' reconnoitring perhaps for whisky.
This seems to suggest that the phrase may have formed as a variation of the phrase pay a call (in use since the early 1800s and itself a variation of pay a visit--in use since at least the mid-1600s). But it could also just be describing the demeanor of the Indians.
The second is substantially earlier and is from Vol. XII of The Oriental Herald, and Journal of General Literature, 1827:
The same feeling forbade to wait the result of a cold call for Colonel J. W. Adams's services ; and the staff of the army was completed before that veteran could recal his leave of absence on account of sickness.
Again, it is unclear what exactly is meant by cold in this citation. It could mean the call was calculated and unfeeling, but it could also imply that it was unexpected.
http://www.bbc.almksb.com/modules.php?name=News&file=print&sid=200
cold call verb and noun (Business World) In marketing jargon, transitive verb: To make an unsolicited telephone call or visit to (a prospective customer) as a way of selling a product. noun: A marketing call on a person who has not previously expressed any interest in the product. Also as an action noun cold calling. Etymology: Formed by compounding: the call, whether by telephone or in person, is made cold, without any previous warm-up, or preparation of the ground. History and Usage: The term was first used in the early seventies as a more jargony equivalent for 'door-to-door selling' (and at that time cold calling was mostly done door-to-door); in the eighties the rise of telemarketing (see tele-) and the emphasis on 'hard sell' has meant a huge increase in cold calling by telephone.
My understanding is that it's a "cold" call because often in sales, how interested a party is in the service you're selling is defined in terms of temperature: a "hot" prospect is interested in your product or service and may be ready to close the deal, as compared to a "warm" lead which could be somebody whom you have heard needs your product or services, but you haven't spoken to directly.
When you make a "cold call", you are calling upon someone whom you have never spoken to and know little about, therefore the lead is "cold" -- you don't know if they will be interested or not. Hopefully (for you) the cold call will produce a warm lead, bringing you closer to a sale. But since "cold calling" is less likely to produce a sale than calling someone you know is interested, it's referred to as "cold" whereas the later is "warm" or "hot".
Interesting to see from the other answers that it does predate the telephone, but this makes since as the verb "call" can also mean to visit somebody in person.
Here's an interesting reference from the A Dictionary of Accounting (Oxford University Press)1 :
cold calling : A method of selling a product or service in which a sales representative makes calls, door-to-door, by post, or by telephone, to people who have not previously shown any interest in the product or service. In the UK, the selling of investments by cold calling is regulated by the Financial Services Act 1986.
As you can see in this example, cold-calling encompasses "making a call" whether by mail, door-to-door, or by telephone.
The usage of "calling" as visiting in person definitely pre-dates the usage of "cold-calling" as well.
1 : "cold calling" A Dictionary of Accounting. Ed Jonathan Law and Gary Owen. Oxford University Press, 2010. Oxford Reference Online. Oxford University Press.
The earliest instances of "cold call" in Google Books search results seem to refer to in-person visits—in the same sense that a "gentleman caller" in The Glass Menagerie is someone who makes a physical appearance at the Wingfields' door, rather than simply ringing Amanda up.
Unfortunately, the link to a snippet view of an instance from a 1925 issue of The American Magazine, which appears in Callithumpian's answer from March 20, 2011, no longer works; and a search for the phrase "cold call, and it won" yields no matches. The earliest matches that Google Books searches yield for the precise phrase "cold call" in its relevant sense are from slightly later.
The 'cold call' and its brethren
However, the term "cold call" is just one of a number of similar expressions that refer to the same activity: walking up to a business or home, knocking on the door, and attempting to persuade the person who answers to buy the product that the salesman is offering. Among the expressions used for this activity are (or were) "cold call[s]," "cold turkey call[s]," "cold solicitation[s]," "cold turkey solicitation[s]," cold selling," and "cold turkey selling."
The earliest such match that I found is from The National Underwriter, volume 22 (1918) [combined snippets]:
The Real Straight Canvass
The straight canvass does not mean going from house to house or office to office and rapping on the door and asking in a timid voice, "Does any one here want any life insurance to-day?" When the straight canvass is referred to it should not call to mind a mere peddling of life insurance. The cold solicitation can be made as businesslike and scientific as the previously prepared canvass. The successful straight canvass man is actually entitled to a good deal more credit than the man who paves the way for every interview he has. The man who can go out on his own resources without introductions, and without friends, and bring home the bacon has a strong character and forceful personality.
From Gas Age-Record, volume 51 (1923) [combined snippets]:
From my experience with me, the three causes of dislike of ringing door-bells are LAZINESS, TIMIDITY, and SWELLED-HEAD.
To get results from "cold" solicitations you must make a relatively large number of calls in proportion to the deals closed. This means work. Ringing from sixty to seventy door-bells a day is not unusual if you want results. This means WORK—and HARD WORK, and you'll be tired at night, but the best motto reads I ever saw for salesmen LEG WORK PAYS and it sure does. But the lazy salesman is not going to make any sixty calls a day if he can pick up enough orders "to get by on," from eight to ten "preferred" prospects. That's why the lazy salesman hates door-to-door work.
From Sales Management, volume 11 (1926) [combined snippets]:
Even in the bond business, where sales are made largely on the basis of customers' confidence in the salesman and his house, which can only be obtained after many calls and friendly interviews, canvassing plays an important part. Kenneth W. Moore, of the American Bond & Mortgage Company, states that each salesman is required to obtain at least two new prospects a week. Before a bond salesman builds up his own list of clients he has to resort almost entirely to making cold calls on persons who are known to be financially able to buy bonds.
From "Cold-Turkey Selling Does Not Pay," in Advertising & Selling, volume 8 (1926) [combined snippets]:
A company that has been spending $250,000 a year to pave the way for its salesmen recently discontinued all promotional effort of this kind. "If a salesman is any good, he ought to be able to find his own prospects," is the only excuse the organization gave for its change in policy.
The company took this action despite the fact that it has been proved in thousands of cases that it does not pay to have salesmen make cold-turkey solicitations. The salesman who goes out to sell, without having his way prepared for him by some form of advance work, exerts so much effort in breaking down resistance and so much time in explaining who he is and what he has that he has neither time nor energy left to do much selling.
From Printer's Ink (October 28, 1926) [combined snippets]:
He [E.D. Gibbs, author of "Using the Mails to Help Sales"] urged each salesman to make up his own small list of prospects and send a few pieces [of promotional mail to them] each day. When they precede the salesman's call they break the ice for him, he pointed out. When they are sent after the call, they help remind the prospect of all that has taken place while the salesman was with him.
...
Mr. McCallister talked about "Today's Responsibility for Selling." He listed six points which sales executives should watch. These are: (1) The management must put a selling idea in the product. (2) It must open up territories and uncover leads for salesmen. Cold turkey selling is one of the hardest jobs any salesman can be called on to perform, (3) The management must advertise the product. ...
From Merchandising Week (September 1928) [snippet view]:
We have an outside selling force just large enough to allow time for following up all store, newspaper and personal leads, plus some "cold turkey" solicitation at the front door. The latter, except on new home prospects, is limited to three calls by any member of the Nicholas Hardware organization on any one prospect.
From The Adjuster, volumes 76–77 (1928) [combined snippets]:
If such an agent could learn a lesson from the department store or could take a warning from the corner grocery by increasing the turn-over in every department of his business by doing more "cold turkey" solicitation of new prospects, by going out after the lines that have never been written, digging up new business through his intimate knowledge of the business itself and of where the new prospects can be found, he would send to his companies enough new, good, low loss ratio business to "sweeten up" the hazardous lines of his agency to the end that his companies, as well as his own agency, would be able to show a satisfactory profit.
From "Cold Selling by Salesmen," in Postage and the Mailbag (February 1929):
The hardest thing in the world is cold selling. A salesman is sent out to a certain territory to make sales. He is given a route-list, the names of alleged prospects in each city or town, a pad of order forms and report blanks. First of all, he must find out the name of the man or woman who can sign the order. When this is done, he begins to explain his proposition to someone who knows nothing or very little, about the product.
After three or four turndowns, the average salesman begins to lose his nerve. He begins to have doubts about his product, then about his selling ability. He spends hours, days or weeks in useless walking and waiting.
From S.K. Hargis, "Warming Up the Cold Printing Prospect," in [Printed Salesmanship, volume 54 (1929) [combined snippets]:
"Cold turkey" calls are a big factor in the building up of any job-printing business. In other lines of business salesmen may successfully pave the way by phone or rely upon personal connections and friends. But the printing scout must ease himself into new doorways every day in the year, often without a name to mention and with a certain percentage of strange faces peering over the desk at him, testing his personal courage, his wit and his training.
...
Some large job shops, knowing full well the futility of this kind of an approach have set about to furnish their cold-call men with something more than material for repartee of that kind. They know that such visits are ineffective, uninteresting and unproductive; they, in fact, rather do damage to the shop in the minds of the prospects.
...
It has been the experience of seasoned job-printing salesmen that the first cold call should never involve a direct request for business or even for a trial order. Business houses do not shift their printing connections over night and the best shop wins in the end. If the first cold call is made interesting enough to establish an entrée, the salesman has done about all he can do until a second call.
From Gas Age-Record, volume 65 (1929) [snippet view]:
If a man is sloppy in appearance, his hair uncut or face unshaven or clothes unpressed, it is more than likely that he will not gain admittance to a home at which he is making a cold solicitation. The housewife is likely to take one look at him and close the door in his face.
From Coleman Everett, "'Cold-Turkey' Solicitations Are a Relic of the Wasteful Age," in Inland Printer, American Lithographer, volume 83 (1929) [combined snippets]:
I hold no brief for the printing salesman who is unsuccessful. One finds the poor hitters, the just-get-bys, in every line of endeavor from which man wrests a living. But there is one angle of a printing salesman's job which cannot be justified on any sound economic grounds by the master printer: that is the proposition of "cold-turkey" solicitations.
The master printer cannot see his salesmen through the eyes of the man who buys printing. But it is simple enough from my chair behind the buyer's desk. ...
This discussion of my company's printing connections may seem to have little bearing upon the "cold-turkey" calls made by printing salesmen at my office every day. But it has a most direct relation, for the printing salesmen who leave their cards for the first time are aspirants for the inner-circle status of our regular printers. ...
Early use of 'cold turkey' to mean 'without advance notice'
Interestingly, "cold turkey" as a descriptive term for withdrawal from drug addiction through sudden and complete removal of access to the drug goes back at least to 1921. From "'Cold Turkey' Treatment," a registered nurse's letter to the editor of the New York Tribune (August 13, 1921):
Sir: I read with indignation the remarks accredited to Dr. Alfred C. Prentice in regard to what he calls the "cold turkey" treatment of drug addicts, meaning, it seems, instant and complete withdrawal of the drug from those afflicted with the drug habit. ...
And "cold turkey" as a synonym for "without warning" is even older. From "Girl Inherits $1,000,000 While on Hawaiian Honeymoon," in the Washington [D.C.] Herald (August 10, 1920):
How would you like to come into an inheritance of $1,000,000 "cold turkey"? A Toledo girl, recently a war worker in France, has done just that. She is Mrs. Margaret Ashley Paddock, daughter of Henry W. Ashley, and granddaughter of Wellington R. Burt, multimillionaire railway magnate of Saginaw, Mich., whose estate has just been divided.
Conclusion
Although the earliest recorded uses of the phrases "cold call" and "cold solicitation" in the relevant sense are not older than the telephone, people who used them during the period 1918–1929 do not seem to have applied them to telephoning strangers and presenting them with a business or sales proposition. Rather, the usage applied to making in-person visits to a prospective customer's home or office. Some of the examples given above refer to knocking on doors; others mention "calling on"—rather than simply "calling"—prospects. Evidently, in the early days of cold calling, sellers did not imagine that solicitation could be successful without direct, in-person contact.