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
At all is simply an intensifying additional element without any inherent grammatical purpose, and is found in other contexts too, not just in the expression 'nothing at all':