The phrase phoney baloney seems to have its popular origin in the term the phonus bolonus, which Damon Runyon uses three times in his very popular 1932 book Guys and Dolls. From Damon Runyon, Guys and Dolls (1932) [combined snippets]:
Of course this message is nothing but the phonus bolonus, but Waldo drops in for it and gets in the car. Then Wop Joe drives him up to Miss Missouri Martin’s apartment, and who gets in the car there but Dave the Dude. And away they go.
…
This Rodney B. Emerson is quite a guy along Broadway, and a great hand for spending dough and looking for laughs, and he is very popular with the mob. Furthermore, he is obligated to Dave the Dude, because Dave sells him good champagne when most guys are trying to hand him the old phonus bolonus, and naturally Rodney B. Emerson appreciates this kind treatment.
…
So he hops right over from Newport, and joins in with Dave the Dude, and I wish to say Rodney B. Emerson will always be kindly remembered by one and all for his co-operation, and nobody will ever again try to hand him the phonus bolonus when he is not buying it off of Dave the Dude.
Runyon's word choice (and diction) prompted this response in a contemporaneous review of Guys and Dolls. From “Broadway in Two Tenses," in The New Republic (“1931”) [combined snippets]:
I am not trying to say why it is, but it seems sure that unless Mr. Damon Runyon is giving one and all the phonus bolonus, the citizens along Broadway have a very quaint way of talking indeed. I do not think it is so much that their pick of words is different from that of the rest of us, for if you will ask me I will say that there is no line of Mr. Damon Runyon’s book which will give a moment’s pain to anyone, even if he never makes it a point to keep watch of the wellsprings of the American language. In fact I will go so far as to say that personally I will talk more slanguage in ten minutes as a usual thing than you will be able to find in Mr. Damon Runyon's book.
Harold Wentworth & Stuart Flexner, Dictionary of American Slang (1960) reports the following early slang meanings of boloney:
boloney baloney bologny n. 1 An inferior prize fighter . 1921: "...To bounce some boloney at this fight club." Witwer, Leather, 28. Never common. See sausage. 2 An An uninformed, stupid, or needless person. 1937: "...You dumb baloney." Wordman, Wholesale, 9. Fairly common until c1940; archaic. 3 Nonsense; false information or talk, even if believed by the speaker; worthless or pretentious talk; tripe, bunk, hokum, hot air, blah. 1929: "...One of the young men ... dismissed the whole speech as 'a bunch of tripe.' The other .... concluded, 'Oh, of course there was a certain amount of bologny in what he said....'" Philip Curtiss, Harper's, Aug., 385/1. ...
Wentworth & Flexner also traces the slang term phoney in the sense of "Not genuine; fake or faked; counterfeit; insincere" to 1902. And finally Stuart & Flexner offers this definition of the phonus bolonus, which it links to Runyan:
phonus bolonus (the) n. Something or someone phoney or of a quality below that represented; anything cheap, gaudy, or of inferior quality; insincere speech, exaggeration, a line; wrong or misleading advice, a bum steer.
To all appearances, phoney baloney is simply an adjectival rendering of "the phonus balonus," with most of its essential meanings retained intact. In short, the words phoney and baloney inspired the phonus bolonus, which in turn begat phoney baloney (in its various spellings).
UPDATE (10/29/14): FURTHER RESEARCH
I did some additional research into the spellings "phony boloney," "phoney boloney," "phony boloneys," phoney boloneys," etc., and found several instances that appear at approximately the same date as Runyan's Guys and Dolls—certainly close enough to raise the question of whether he simply faux-Latinized a slang term that was already current, as bib suggests in a comment below.
The oldest possibility is tantalizingly early—it's a song title that appears in a snippet view taken from Library of Congress, Catalog of Copyright Entries: Musical Compositions, Part 3, supposedly from 1930—but also extremely bare-bones:
That phoney boloney. 2162.
However, Frank Hoffman, Dick Carty & Quentin Riggs, Billy Murray: The Phonograph Industries First Great Recording Artist (1997) show a song of that name (albeit with Baloney instead of Boloney) appearing on three 78-rpm recordings issued by three different labels during 1929 [snippet view]:
That Phoney Baloney. (Samberg, Pestalozza) Solo. Banner 6280. Side B. 1929.
That Phoney Boloney. (Samberg, Pestalozza) Solo. Domino 4285. 8469- 2. Side A. 1929.
That Phoney Baloney. (Samberg, Pestalozza) Solo. Oriole 1469. 1929.
Another interesting early reference to the term occurs in Cornelius Willemse, A Cop Remembers (1933), which devotes an entire chapter to the topic of “Phony Boloneys” and includes this comment:
It was just another "phony boloney," designed to cheat the insurance company and it wasn't very well done at that. It was years afterwards that I dug up some more information on this case.
The fact that Willemse's book is a memoir suggests that "phony boloney" may have existed as slang for a particular category of scamming crimes—at least in New York City, where Willemse worked as a policeman and detective for 26 years, between 1900 and 1925, according to the Wikipedia article about him—for some years prior to 1933.
Perhaps the most interesting feature of these early instances of phoney [or phony] boloney is that the term appears as a noun in each instance—just as in the case of Runyon's the phonus bolonus. At this point I'm inclined to think that Runyon simply borrowed and gussied up an existing New York City slang term for his book.
Best Answer
Early (1939–1943) cultural and etymological inquiries into 'zoot suit'
American Notes & Queries, volume 3 (July 1943) has this interesting commentary on zoot suit [combined snippets]:
According to Allan Metcalf, From Skedaddle to Selfie: Words of the Generations (2015), the song "A Zoot Suit (for My Sunday Gal)" (written in 1941) matches a boy's desire for a "zoot suit with a reat pleat/And a drape shape, and a stuff cuff" with a girl's desire for a "brown gown with a zop top/And a hip slip, and a laced waist." The song was written by Ray Gilbert and Bob O'Brien—white song composers who presumably were not part of the Harlem "slang rhymes" scene but who had probably been strongly influenced by Duke Ellington's 1941 Jump for Joy show, which, according to Kathy Peiss, Zoot Suit: The Enigmatic Career of an Extreme Style (2011), "brought the zoot suit to center stage as a symbol of expressiveness, fluidity, an freedom."
The February 1940 New York Times article cited in American Notes & Queries (above), as condensed for Negro Digest, volume 1 (1943) [combined snippets], offers the following glancing comment on the origin of the name zoot suit:
The item in The New Yorker (June 19, 1943) [combined snippets] cited by American Notes & Queries (above) says this:
Earlier than any of these instances are entries from Cab Callaway, "Hepster's Dictionary" (1939):
If the American Notes & Queries note (above) is correct in arguing that zoot originated as a corruption of suit, it follows that Calloway's claim that zoot means "exaggerated" is evidence that zoot (as a stand-alone adjective) arose after the term zoot suit did, and drew its meaning from the oversize dimensions of the suit.
'Zoot' before the suit
As for pre-1940s mentions of zoot in Google Books search results, all of the ones I checked proved to be OCR garblings, occurrences in misdated publications that were actually from later than 1941, or nonsense syllables, as in this instance from Marie Nelson Lee, "The Tuneless Fiddle," in By Special Request (1921):
So there is no record—in Google Books search results, anyway—of zoot as a meaningful term prior to the debut of the phrase zoot suit in the late 1930s.