'Shoot the breeze'
Christine Ammer, The American Heritage Dictionary of Idioms, second edition (2013) offers this entry for the idiom:
shoot the breeze Also shoot or throw the bull. Talk idly, chat, as in They've been sitting on the porch for hours, just shooting the breeze, or The guys sit around the locker room, throwing the bull. The first of these slangy terms alluding to talking into the wind, was first recorded in 1919. In the variant, first recorded in 1908 bull is a shortening of bullshit, and means "empty talk" or "lies."
The structure of Ammer's entry implies that "shoot the breeze" is the primary wording and that "shoot [or throw] the bull" is the variant, but this seems at odds with the first occurrence dates that she provides: 1919 for the former and 1908 for the latter.
The earliest instance of "shooting the breeze" that a search of the Library of Congress's Chronicling America newspaper database turns up is from "Richmond Man Shows Up Champ" in the Richmond [Indiana] Palladium and Sun-Telegram (June 27, 1914):
When G. L. Kinsburg, the Brooklyn checker champ, made the rather large assertion that he would hold his own with a dozen men at one time, "he was not shooting the breeze," but nevertheless his performance of this stunt was a bit dimmed when one particular G. P. Clawson, a Richmond man, tuned the trick on the champ two out of three. Whether Kingsburg was just laying down on his job or nor is unknown. Kingsburg claims to be the juvenile checker champ of the world, and is making a tour of the states giving exhibitions of his prowess.
Ammer may be correct that this version of the expression alludes to "talking into the wind"; alternatively, however, it may refer to emitting a steady stream of light wind—that is, "blowing air"—as a fan does. Two fairly early examples of fan-specific "breeze shooting" appear in Chronicling America search results. From "Organized Wealth," in the Casper [Wyoming] Daily Tribune (July 23, 1924):
We are dictating this editorial to a young woman sitting at a typewriter. ... Over in the corner there is an electric fan which revolves. It is a wonderful fan. Every two seconds it shoots a breeze across the desk and against the young woman at the machine. Every two seconds it fans the wind through the thinning hair of us who dictate.
And from an advertisement for Palais Royal in the [Washington, D.C.] Evening Star (July 20, 1932):
Breeze!
9.95 Noiseless Oscillating Fan
As they turn back and forth and shoot cooling breezes into every corner of your room, you'll forget the heat . . . if you have one of these fans! 9-inch brass blades, a powerful motor, and guaranteed for one year.
This seems consistent with the description of the expression in "Shoots a Breeze" in the Hendersonville [North Carolina] Times News (June 2, 1934):
ABOARD U. S. S. INDIANAPOLIS. New York. June 2.—(UP).—President Roosevelt frequently visits this ship and he "always shoots a breeze" bluejackets said yesterday. That's navy for chatting pleasantly.
From roughly the same time period, in an unidentified item in The Nineteen Thirty One Lucky Bag: The Annual of the Regiment of Midshipmen (U.S. Naval Academy, 1931) [combined snippets]:
stories have made Gus the leading man in almost every bull session. And can he shoot the breeze? Without a doubt he is the unquestioned champion of the Regiment. He is the originator of all bad dope and the father of no-soap jokes. Cheerful—good natured—the world may trample him— the temporary weakness may go back on him, but he always comes up smiling. Sure he can gripe, just like the rest of us, but he never really means it.
And from "Nicaragua: Patio Patter," in The Leatherneck (March 1932):
Another thing that has to be added to the bright side of things in Nicaragua is the "Enlisted Men's Club." There we can gather and spend the afternoons to please ourselves, shoot the breeze, and have quite a bit of fun. All Marines like to gather in some nice place to have their daily pow pow and the Enlisted Men's Club is an ideal place.
'Shoot the bull [con]' and 'throw the bull'
Instances of "shoot the bull [con]" appear as early as 1906. From "Dope of the Day," in the Minneapolis [Minnesota] Journal (August 25, 1906):
Is it loyalty to the club that represents their city, or are the fans suckers, to support a second-division or tail-end team season after season? It is the same gag with all these phony outfits. Each spring the manager and owner begin to shoot the bull con about what the team is going to do the coming season.
"We are not claiming the pennant," says the manager, "but the club that wins it will have to beat us." And the club that wins the flag does beat them, something like 17 out of 20 games.
Verified instances of 'throw the bull [con]" are even earlier, which is not surprising given that the literal feat of "throwing a bull" by grasping it by the horns and flipping it over by main (leveraged) strength appears to have been a major attraction in the late 1800s and early 1900s as a way for strongmen to prove their prowess. From an untitled item in the Houston [Texas] Daily Post (September 17, 1897):
The loyal democratic league of New York has served notice on Trust defender Flower and Wolfert's Rooster that they can't throw the "bull con" into the free silver democracy of that state.
From an untitled item in the [New York] Sun (January 1, 1898):
"Say!" ejaculated the leader [of an impromptu band of musicians who had stepped into a boxing ring in Buffalo, New York, to entertain an audience that had come to see a boxing match that had been delayed due to arrest warrants issued to both prize fighters]. "We don't know a thing. Why if we get up in der ring ag'in der mob'll steal our instruments. Some o' you [fight] managers get up dere and throw der bull con into 'em. Dey'll stand fer dat, but nort fer music." The musicians fled.
From an untitled item in the [Stillwater, Minnesota] Prison Mirror, edited and published by inmates of the Minnesota State Prison, (October 6, 1898):
One of my constituents informed me the other night that the Spaniards would throw a bull con into our peace commissioners. He probably has some reference to the Spanish love of bull fights.
From "Florida," in the [Savannah, Georgia] Evening News (March 7, 1900):
Bunco men are in Jacksonville and are doing their work almost every day, but they made a bad break when they tried to beat S. E. Steppins, a resident of Fairmount N. D., who, with his wife, is there for the winter, as he reported their workings to the police before they had an opportunity to "throw the bull con into him," as the work is known in the language of crooks. The crooks probably smelt a mouse, for they did not meet their appointment with Steppins, and the police did not get them.
From "A 'Trusty' Drummer: He Drops into 'The Optic' Office and Dashes off Some Copy," in the Las Vegas [New Mexico] Daily Optic (September 25, 1900):
"The American people," says the trust attorney, "are a lot of juicy lobsters who don't know their living and positively deserve their impending fate. We buy up the newspaper columns at $1 a line and throw the bull con into 'em very easily."
And from "Fights and Fighters," in the Waterbury [Connecticut] Democrat (November 8, 1900):
Now this fellow [Dave] Sullivan has no intention of ever meeting Terry [McGovern]. He is a bluffer and is at Louisville throwing the "Bull Con" into the sporting fraternity. He finds that hew can do it no longer in New York, so he thought he would go down among the colonels and make them believe he is the real champion.
J.E. Lighter, Random House Historical Dictionary of American Slang (1994) has this entry for "bull con":
bull con n. {BULL + CON} exaggerated or lying talk; (hence) SNOW JOB. Also bullcorn. Also as v. [Earliest cited reference:] 1896 Ade, Artie 26: I may be a farmer, but it takes better people than you to sling the bull con into me.
"Ade" is George Ade, and the cited book is Artie: A Story of the Streets and Town (1896). Interestingly, in Ade's example and in several of the earliest instances of "throw the bull con" noted above, the action is said to go "into" the object of the slinging or throwing. I don't know why this should be so.
Louis Jackson & C.R. Hellyer, A Vocabulary of Criminal Slang: With Some Examples of Common Usages (1914) conveniently offers coverage of the noun forms of "breeze," "bull," "bull con," and "con":
BREEZE, Noun | General usage. Loquacity; guile; "hot air;" ["]bull con."
...
BULL, Noun | General usage. Misrepresentation; a lie; deception. Probably derived from the financial term bull, which in polite and legal circles signifies inflation, optimism. See "BREEZE." Also used to indicate an officer of the law whose function is to apprehend or arrest, whether a constable, marshal, sheriff, detective or policeman.
BULL CON, Noun | Supra idem.
...
CON, Noun | General usage. A convict; a lie; a misrepresentation. See "BUNK" [defined as "Deceit; ostentation"].
Other early variants
In addition to "shoot the breeze," "shoot the bull," and "throw the bull," slang dictionaries note at least two other variants. From Maurice Weseen, Dictionary of American Slang (1934):
Shoot the lemon—to converse informally. [Identified as "Crooks' and Criminals' Slang"]
...
Shoot the bull—To talk nonsense; to talk insincerely. Shoot the baloney is a variant. [Identified as General Slang]
And from Hyman Goldin, Dictionary of American Underworld Lingo (1950):
Shoot the lemon. (Leavenworth Federal Prison) To sit around telling stories, especially of exploits.
The earliest Google Books match for "shoot the lemon" is from "Dictionary of Prison Slang," in [Fort Leavenworth, Kansas] Stray Shots May 15, 1919):
Shoot the lemon—talk
"Shoot the lemon" thus appears to be almost as old as "shoot the breeze."
Chronological summary of the 'shoot the breeze' family of expressions
Here in summary form are the earliest confirmed occurrences of the 'shoot the breeze' family of expressions from earliest to latest:
throw the bull con: by September 17, 1897
shoot the bull con: by August 25, 1906
shoot the breeze: by June 27, 1914
shoot the lemon: by May 15, 1919
shoot the baloney: by 1934