From my grandfather:
*Habenzie Gabenzie
Shitballs in the morning
Duke Monaghan, Duke Monaghan… (ad nauseam, to the tune of “Carol of the Bells”)
Old McAlears
You gotta go to Valparaiso
Bat in the mouth and a haircut
Enoch and Anacanascram*
There are dozens more, but these are a few that leap to mind. These expressions are uttered under very specific circumstances, such as any circumstances at all for no particular reason.
Thanks to Yakko’s song from “Animaniacs” where he names all the countries in the world, I’ve been using “Dahomey Namibia!” as an expression of dumbfounded amazement.
How about Darren McGavin’s phrase from Christmas Story:
Filthy rotten house-stickle-pfeiffer!!
Ooh, beat me to the punch, interface2x.
Although the one I use (since my daughter started figuring out how to repeat everything I say, anyway) is “Nottafingah!”
I think that’s it, anyway… said as he comes upstairs to ‘deliver a crushing retort.’
It feels just… visceral enough, I guess, to replace f**k, when said with great vehemence. 
Surely, it is most often used in phrases like:
“He/She looks as though butter wouldn’t melt in his/her mouth”
and is typically meant to imply that someone is not so innocent as they seem.
See, The Phrase Finder which gives:
“Meaning
Prim and proper.
Origin
The allusion is to women who are so proper that they don’t even have the warmth to melt butter. Is recorded as being in use since 16th century”
A former boss of mine used to say “Abyssinia” instead of “I’ll be seein’ ya”.
My mom’s phrase for “speed it up, willya”:
Since I don’t know if faster-moving people have live flies falling off them or if they have dead flies that stay put, I’m nominating it.
cuauhtemoc, those are some good ones. Truly random and meaningless! I also like gonzoron’s “Tachometers!”
dantheman, another good one meaning “far away” or “the middle of nowhere”: several of my New Jersey friends refer to rural locations as “out in Bumblefuck, NJ”. That may have a pop culture source that I’m not familiar with; I’ve never asked them for an explanation.
-Andrew L
It’s from the lyrics to Nanook Rubs It
“Godfrey Daniels!”
Something I still use that I picked up from my 6th grade history teacher Mr. Seaman is, “Now you’re cookin’ with Ajax!” I have no idea where he got this from or if he coined it, so far I haven’t bumped into anyone else familiar with the expression. I figure if someone else has heard it, this would be the place.
Well, “now you’re cookin’” or “now you’re cookin’ with grease” are standards so he jazzed it up a little ?? Like “the devil’s avocado”.
In high school, I was friends with an exchange student from Brazil. Apparently, (maybe a South American Doper could enlighten me) there’s a Brazilian colloquialism, “travelling in the mayonnaise” which means that someone is being silly or absurd. My friends and I adopted the expression. Eventually, we would just shake our heads and say “Mayonnaise” when referring to such situations.
Our variations are “Buttfuck Nowhere”, also known as St.-Denis-de-Brompton 
Actually, SDdB is a real place, but since it seems like every highway in Quebec has an exit for it, we figured it just probably lead to nowhere, and the government just wanted to be polite about it!
The other name we use for middle of nowhere places is “St. Pit-de-Nowhere”. The thing about Quebec is that EVERY TOWN IN THE PROVINCE is named St-something-or-other. There are a lot of Quebec Saints, apparently, or its all the same guys who happened to live in a bazillion and one places
When I lived in NJ (for 30 years!), it was Bumfuck, Egypt. Why they picked on Egypt, I’ll never know.
You’ll be bangin’ your head on a blind alley.
Perry White’s ghost!
Pelchi MacSnoo.
Fottlydot
E Pluribus Gad!
Jesus Ramirez.
googly-eyed goes back to at least 1901. So it wouldn’t be hard to understand such a word becoming “googly moogly.”
KInda like someone saying “Geez!” and then comes “Geezy Peezy.” Etc. Or Geez Louise.
Perry White being the editor of the newspaper on which Superman/Clark Kent worked. And he kept saying “Great Caesar’s Ghost!” as an epithet.
We did a thread on “Bumfuck” I think. It is cited from the early 1970’s in print but I’m sure it goes back to military in the 1960’s or earlier. I surmise it came from the use of “Bumf” which was short for “bum fodder” which was “toilet paper” or any worthless piece of paper. NOt hard to imagine soldiers taking “bum fodder” and coming up with a phrase “Bum Fuck Egypt”
When my siblings and I messed things up at home, my mom always said we had “strung things from hell to breakfast.” Don’t know exactly how far that is, but I use the same expression with my kids!
I remember, too, asking my parents, “What for?” to which they would reply, “What fer? Cat fur, to make kitten britches!”
If you asked my husband’s family why they did something unusual or trivial, you would likely hear “Oh, just for T-A-D!” I have NO clue as to what that means!
Buggerit Millennium