Of possible interest to the question of phrase origin is this French instance of
"bada bing" from André Rivillet, Maurice Chevalier: De Ménilmontant au Casino de Paris (1927):
Bing, ba da bing... bing...
Une syllabe par pas. Dans le hall du Palace, Maurice étudie des danses anglaises. Un artiste, Johns, un jeune garçon qui a vu et écouté les nègres de Broadway et dont l'œil enferme les pas pour les faire reproduire par les jambes, danse devant lui... Ses jambes croisent, il se déhanche. On dirait, à certains moments, qu'il fauche avec ses pieds; à d'autres instants, il rase le sol et semble prêt à s'envoler. Ce professeur est consciencieux; il appelle au secours de sa démonstration ce langage des durées, dont le bruit approximatif se réduit : Bing, bada, bing.
This passage translates roughly (that is, by way of Google Translate) into the following English:
Bing, ba da bing... bing....
One syllable per step. In the hall of the Palace, Maurice studies English dances. An artist, Johns, a young boy who has seen and listened to the Negroes on Broadway and whose eye locks in the steps to reproduce them with his legs, dances in front of him... His legs cross, he sways his hips. It seems, at times, that he mows with his feet; at other times he skims the ground and seems ready to fly away. This professor is conscientious; he calls to the aid of his demonstration this language of durations, whose approximate noise is reduced: Bing, bada, bing.
This odd instance appears to be a French writer's rendering (in French) of a nonsense syllabification by a young artist with an English last name who has studied the dance moves of "les nègres de Broadway" and is demonstrating them to Maurice Chevalier. Obviously, this is a French occurrence, not an English one, but I think it is nevertheless noteworthy in two ways: (1) it is significantly older than the 1965 instance attributed to Pat Cooper, and (2) there is no evident Italian-American influence on the usage. It is at least possible that the young artist Johns really did voice a series of sounds that resembled "bing bada bing" as he danced, and that he was a native English speaker.
Although it isn't a clearcut instance of English language usage, the example does link "bada bing" to France in 1927. Another instance from France pops up in The Gramophone (1969), in a song title by Gilbert Becaud [combined snippets]:
Becaud's talent doesn't stand still, and his latest album "GB—Gilbert Becaud" (Decca SKLR4997 | LKR4997) he offers his latest image, singing in the most up-to-date French style, but in English. This is an excellent record with quite a new sound, and amongst his best tracks are Don't look back; Bada Bing Bang Bong, My little light and The show is over for tonight.
In English language version of the song, Becaud uses the phrase "bada bing bang bong" to indicate the sudden appearance of things seemingly out of nowhere.
"Bada boom" likewise has a track record in French as an imitative sound, in this case going back to at least the 1870s. From an excerpt from The Goncourt Journal dated 1873, translated and quoted in Paris and the Arts, 1851–1896: From the Goncourt Diaries (1971) [combined snippets]:
And there they were, Daudet, Lépine the musician, and Morny himself in the skull cap and big dressing gown in which he liked to play the Cardinal-Minister, jumping on footstools and beating out loud sounds of "zim boom, zim badaboom" while the Ministers of the Interior and of the Police chewed their nails!
A different translation, from 1962, by Robert Baldick, appears in Edmond & Jules de Goncourt, Pages from the Goncourt (1971) concurs on the "zim boom, zim badaboom" wording, and dates the incident to early (before March 18) 1873 [combined snippets]:
... waiting in the anteroom, were completely forgotten. With the result that while Daudet, the composer L'épine, and Morny himself, wearing the skull-cap and the long dressing gown in which he aped Cardinal Richelieu, were all three of them jumping about on stools and singing: 'Zim boum, zim badaboum' at the top of their voices, the Ministers of the Interior and Police sat twiddling their thumbs outside.
From "A Decoration Won" The Elocutionist's Journal, (autumn 1877):
"Sacrebleu! General, explain to me what that blackguard of a lancer is doing oin the middle of the empress' dragoons. The emperor is very much displeased!"
"H———s fire marshal! I had not remarked it. I shall go and find out what that means."
And the general of the division, commander-in-chief of the cavalry of the guard, trots—badaboom! badaboom! badaboom!—until he has found the general of brigade, chief of the general staff.
The Elocutionist's Journal was a periodical published in New York City, and the instance of imitative "badaboom" quoted above may be an original English composition. Nevertheless, the piece has a strong French inflection, with badaboom following close on the heels of sacrebleu in a vaguely Napoleonic setting.
From Theodore Botrel, "A Rain of Bombs" in a section of Harvey Grumbine, Humanity Or Hate: Which? (1918) titled "French War Songs":
A rain, a rain of bombs, / (Boom, boom! Very bad! Badaboom, bom, bom!) / A rain a rain of bombs! / Go into the house! Run, run! / Run run!
Go into the house! Run, run!
It's Death, it's Death that comes, / (Boom, boom! Very bad! Badaboom, bom, bom!) / It's Death, it's Death that comes / Flying against the sun!
It also appears in a 1948 translation by Lloyd Alexander of Jean-Paul Sartre, "The Childhood of a Leader," from The Wall and Other Stories (1939/1948) [combined snippets]:
It was amusing because everyone was playing. Papa and mama were playing papa and mama; mama was playing worried because her little darling wasn't eating, papa was playing at reading the paper and sometimes shaking his finger in Lucien's face saying, "Badaboom, little man! And Lucien was playing too, but finally he didn't know at what. Orphan? Or Lucien?
And from a 1951 translation of Henri Troyat (a Russian-born French writer), My Father's House: A Novel (1946/1951):
"This time the thunder will be very near," said Tania. "Very near . . ." and she started to count, "One, two . . ."
A tremendous roll of thunder interrupted her.
"Badaboom!" howled Akim, running to the window. "I'm going to see if anything's on fire."
None of these various French or French-influenced occurrences of "bada bing" and "badaboom" (or "badaboum") use the two expressions as a single phrase, but collectively they offer at least some circumstantial evidence that the expressions may have arisen independently in French as imitative sounds, although I a haven't found any instances from the pre-Sopranos era in which they were used consecutively in that language. The matches from before 1965 that Google Books and Elephind newspaper database searches turn up do not suggest a comparable connection to Italy or to Italian-American usage.