Roy Zimmerman's song "Firing the Surgeon General" established the title phrase as a euphemism for masturbation (by paralleling it to a number of other such euphemisms) to satirize the controversy that resulted in the 1994 dismissal of Surgeon General Joycelyn Elders.
Limp Bizkit's Chocolate Starfish and the Hot Dog Flavored Water. "Chocolate starfish" here being a euphemism for asshole, while "hot dog flavoured water" comes from an in-joke about how Wes Borland saw flavoured water on sale at a truck stop while touring, and jokingly wondered if they also come in meat or hot dog flavour.
When Emilie Autumn performed her song "Misery Loves Company" on a morning news show, she replaced the line "pray for me you fucker, if you fucking dare" with "pray for me you muffin, if you muffin dare".
The song "Mutha'Uckas" and the term Muther'flippin from "Hiphophippotomous Vs. Rhymnocerous"
Played with in the music video for "Laid" by the band James. One line originally goes "But she only comes when she's on top." The version used in the music video replaces "comes" with "sings" - but that part of the video has a close shot of the lead singer, who is obviously singing the original lyric.
Originally composed for the alt.games.nintendo.pokemon.hentai newsgroup, the song "I Wanna Slowpoke Your Cloyster ('Till My Bulbasaur)" introduced the title phrase, as well as "jiggling the Jigglypuff".
"The Fez" by Steely Dan isn't about a hat. It's a (made up?) euphemism for a condom.
But then "Steely Dan" is a euphemism for an erection, so that's hardly surprising.
Steely Dan actually took their name from the nickname for a large metal dildo in Naked Lunch.
Viktor Vaughn's song "Mister Clean" has little to do with cleaning supplies; the title refers to Vik's insistance that his barber "Give me a Mister Clean", or shave his head completely, at the end.
Vik has a lot of strange or unique words or phrases. At one point he reminisces about something that happened "six degrees ago", etc.
The same artist does something similar in his Kind Geedorah persona; Geedorah is a space monster who doesn't truly understand humanity, and his alien perspective is partially represented by some seriously idiosyncratic speech quirks.
In the Meat Loaf song I'd Do Anything For Love (But I Won't Do That), "that" is a reference to a previous line where the singer names a thing he would never do ("forget the way you feel", "stop dreaming of you", etc.) Due in no small part to the complexity of the lyrical construction, it's also assumed by many listeners to be a euphemism for something else, to the point where Meat Loaf says "What is that?" is the most frequent question he's asked by his fans.
"Elektronik Supersonik" by Zlad! includes the lines "I put my port plug in your socket" and "So onto my love rocket, climb."
Rammstein does that kinda often as well. Most notably in Pussy. Blitzkrieg mit dem Fleischgewehr!
A radio edit of Jethro Tull's "Locomotive Breath" removed "balls" and spliced in the word "fun" from the previous verse, resulting in the strange expression "got him by the fun."
Starflyer 59: While their lyrics never use any words worse than "hell", Jason Martin reportedly used (and possibly still uses) euphemisms like "what the eff" and "piece of shin".
Steeleye Span's "Drink Down The Moon" uses "cuckoo's nest" to refer to female genitalia.
Aerosmith songs are full of this. Most notably the famous Walk This Way has this line "You ain't seen nothin' 'till you're down on a muffin." Lady Gaga's line in Poker Face is probably a Shout-Out to this song.
"Muff" may be dated, but it's not an unusual expression, at least not in 1975.
Insane Clown Posse use the terms "Neden" and "Cotton Candy" over "vagina" or "pussy"; other Psychopathic Records artists have used this term as well: Anybody Killa released a song called "Your Neden's Haunted", loosely about sexually-transmitted disease ala ICP's "Bugz On My Nugz".
"Precious" by Pretenders has "I had my eye on your imperial". It doesn't sound like she means a car. More like a scepter.
A possibly once-common expression, used to give an old-fashioned feel to John Fogerty's "Centerfield": according to Word of God, "Brown-eyed handsome man" is an old-time expression for "African-American". Might also pop up in Van Morrison's "Brown Eyed Girl" and Led Zeppelin's "Good Times Bad Times".
I got a dress that'll show a little uh uh But you ain't gettin' uh uh if you don't come pick me up
"Hey Bobby" by K.T. Oslin:
Would you like to for a ride in the country with me
"House of Fun" by Madness is about a teenage boy trying to buy condoms from the chemist, but is too embarrassed to actually say "condoms", so he uses euphemisms that the poor lady behind the counter doesn't understand.
The music of Devo is chock full of strange, obscure euphemisms, an extreme example being their demo song "Goo Goo Itch":
Itchy, itchy goo, there's a pile next to you
Itchy goo, itchy goo and it's turning blue
Itchy goo, itchy goo, itchy goo, goo, goo
It's all I want to do, whammo!
Nobody (apparently even Jerry Casale) is quite sure what "Sloppy (I Saw My Baby Gettin')" is about.
I saw my baby yesterday
She spent her money on a car
It didn't get her very far
So my baby said to me
You know my baby she said sloppy
I think I missed the hole
"Be Stiff", if you can discern the lyrics to begin with, has lines such as "Fruit ooze is wetly lewd, so stay dry in rubber boots," "Cucumbers ripe and rude," "Breathe hard in metal suits," and so forth.