With a little luck, anagrams can make for fun nicknames. Use an anagram generator and you might find something golden. I haven't found anything great in the few times I've tried, but it's got potential, and it's sick.
Other than that...
Linoone - Klepto, Sly Cooper (for sets with Thief)
Shiny Roserade - BlackMagic
Tangrowth - Mojambo (much cooler Japanese name)
Machamp - *insert favorite WWE Superstar*
Bronzong - The Green Lanturn (Shoddy only I'd imagine)
Marowak - Get Bwned, UGotBwned, Teh Bwnzor, PureBwnage, Pwnmerang, Mr. Lonely, etc.
Shiny Nidoqueen - *insert reference to pink tits (mah favorite)*
Shiny Lickylicky - Buddha
Hall of Shame:
Physical Salamence - Draco, Draco Fear, etc.
@Lorak - Is that stupid self-memo really necessary to put in your sig? And is that stuff even remotely difficult to remember? Just wondering, lol.
@TC: You should make a Hall of Fame for the best ones/your favorites.