I have googled but can't find any reference to this. Does anyone know the origin of this phrase (recently used by Trump to refer to the London Mayor)
"Stone cold" is a common informal adjective. Using it to modify "loser" is not remarkable.
(Note that references tend to say it means "completely cold", without giving the inference. In practice it can mean either "cruel" or simply "absolute".)
As other answerers have noted, "stone-cold" as a modifier means "total or absolute." The longer phrase "stone-cold loser" is not an established idiom in general U.S English, as evidenced by the fact that a Google Ngram search for "stone cold loser" yields too few matches to produce a frequency diagram. Nevertheless the term does show up in published writing—and, in particular, in legal writing—going back more than fifty years.
'Stone-cold loser' in legal and political contexts
The earliest match for the term is from an English source: Joshua Casswell, A Lance for Liberty (1981) [combined snippets], writing about a celebrated London murder trial from 1946:
Weak though our case was in law, it still might have succeeded if our medical expert had been really convincing in the witness-box. I do not want to heap too much blame on Dr Hubert's head, especially now that he is dead. The fault for the jury's adverse verdict may well have been entirely mine, or it may simply have been that Heath's case was in any event an almost certain stone-cold loser, legally speaking.
Certainly, Dr Hubert 'came up to his proof,' as lawyers say, in his examination-in-chief. In answer to my questions he gave me nearly all the right answers. But his performance in cross-examination was quite ghastly. Anthony Hawke, with his customary bland courtesy and softly spoken voice for ever saying with each new biting query, "With great respect, Dr Hubert," was quite deadly.
If this were an isolated instance, I might suppose that Casswell's remark about a case's being "an almost certain stone-cold loser, legally speaking" had no special resonance in lawyer-speak. But a surprising number of the Goggle Books matches for "stone-cold loser" occur in legal—and, later, political—settings.
From "Labor Law Reform" in University of Detroit Journal of Urban Law (1979) [combined snippets]:
Labor reform legislation failed to pass the Ninety-fifth Congress [1977–1978] despite strenuous efforts on its behalf by the administration. During the first session of the Ninety-sixth Congress , the administration presented high priority and highly controversial legislation to Congress, including: implementation of an anti-inflation package, revised energy proposals, hospital cost containment legislation, broad revision of international trade laws, and, perhaps, most importantly, Senate ratification of the SALT II treaty. In view of these pressing issues, the administration apparently decided at an early point in the first session of the Congress that it could not afford to spend the few precious Congressional chits it had left on an all-out push for what very well could have again turned out to be a stone-cold loser.
From American Law Reports, ALR 4th, Cases and Annotations (1981), citing a 1978 case, Pennsylvania v. Napper [combined snippets]:
The court held that the defendant had been denied effective assistance of counsel where his attorney had failed to advise him that accepting the prosecution's plea bargain offer of from 12 or 18 months to 3 years on both indictments had considerable merit in view of the fact that the case "was a stone cold loser," and that the sentence could have been—and was—10 to 40 years. The court held that defense counsel has a duty to communicate to his client, not only the terms of a plea bargain offer, but also the relative merits of the offer compared to the defendant's chances at trial.
Q. [PCHA Counsel]: Do you recall him [appellant] being aware that there was substantial incriminating evidence in this case?
[Trial Counsel]: I'm aware that it was a stone cold loser.
Q. Were you aware at that time?
A. I was aware at that time.
THE COURT: By stone cold loser, you mean the case was—
[Trial Counsel]: The case could not have been won.
From Donald Thomas, The Marquis de Sade (1992):
Pauvert as publisher and defendant, was the first witness. It was likely that his case was a stone-cold loser from the start. If not, it soon became so. He began by announcing his duty to give the works of Sade to the French public, as texts of the greatest importance. This democratic right of free people to read their own literature was also the foundation of Maurice Garçon's argument. The president of the court then asked the publisher if Sade's books were not obscene. Pauvert agreed they were obscene but insisted that his editions were not an offence against public morality since he had issued them in limited numbers. It was almost the worst answer that could have been given.
From S.A. Paolantonio, Frank Rizzo: The Last Big Man in Big City America (1993) [snippet view]:
First off, Democratic Party regulars wanted to have little to do with Rizzo after the stunt he pulled with Richard Nixon [supporting Nixon]. What's more, Camiel knew that Rizzo's popularity was beginning to sink in the face of questions about his new home and a public school teachers strike that dragged on through the early weeks of 1973. A Rizzo-backed candidate was a stone-cold loser ...
And from Lisa Scottoline, Everywhere That Mary Went (1993):
We're sitting at a chestnut-veneer conference table to discuss my new case, Hart v. Harbison's, which, to my dismay, is a stone-cold loser. I'd spent the cab ride to the courthouse skimming the thin case file as I looked out the window for the dark car. I don't know which worried me more. I've seen bad discrimination cases in my time—evidence of the shitting upon of every minority in the rainbow—but Hart was the worst. I'd settle the case instantly if it were up to me, but I have a mission. Search, destroy, and petition for costs.
As Chris H astutely observes in a comment beneath this answer, all five of the legal references to "stone-cold loser" cited here refer to a particular case as the loser, whereas the political usage refers to a person as the loser.
'Stone-cold loser' in Donald Trump contexts
A Google Books search reports some nonlegal, nonpolitical instances of "stone-cold loser"—again with the loser in question being a person—from as early as 2004—and two of the earliest such examples come from ... pre-political Donald Trump.
From "The Donald's Private Dick: Did Trump Put a Gumshoe on a Times Reporter's Trail?" in New York magazine (2005) [combined snippets]:
In a peculiar act of media criticism, Donald Trump is telling people that he hired a private investigator to dig up dirt on Times reporter Timothy L. O'Brien, according to a source in Trump's office. The author's Trump Nation, which argues that the developer is more P. T. Barnum than Bill Gates, hit stores in late October to much complaining by its subject. Trump is "the best publicist I could have ever hoped for," says O'Brien, who expresses doubt that he is being tailed and suggests that Trump, whom he covered for fifteen years, has manufactured the P.I. story to intimidate him. "He can dig all he wants—he's not going to find anything," O'Brien says with a laugh.
Trump, asked flat-out whether the story is true, responds thus: "He'll find out soon enough if I hired a private investigator." He also calls O'Brien "a stone-cold loser" and notes that "the whole beauty of this thing is that his book is a resounding failure." Warner Books estimates that it's sold about 4,000 copies so far (BookScan recorded 2,200 in the first month).
And in a CNN interview in 2006 or 2007 on the Anderson Cooper show, speaking of Rosie O'Donnell:
"If you looked like Rosie you'd be critical of beauty pageants, believe me. Rosie is a very unattractive woman, both inside and out. And as hard as it is to believe, inside is probably uglier than outside, and that's really saying something... But you have to understand, I know Rosie. Rosie's a loser. Rosie's been pulling the wool over people's eyes for a long time. She is a stone cold loser. What she is is a bully. Rosie says a lot of things about a lot of people. Nobody... they don't do anything about it. I did something about it."
So Trump's characterization of Sadiq Khan, the current mayor of London, as a "stone cold loser" is actually the third well-publicized instance in which Trump has used that expression to describe someone he dislikes. It is possible that "stone-cold loser" is idiomatic for Trump even though it evidently is not for U.S. English speakers as a whole. It is entertaining to speculate about whether Trump may have learned the expression from one of his lawyer pals (Roy Cohn? Michael Cohen?) but the only way to know for sure would be to ask Trump—and then believe whatever he told you. In any event, there is something pleasing (to me) in the possibility that someday, in the fullness of time, the expression that Donald Trump will be most closely associated with is "stone-cold loser."