(If you want more backstory or more difficulty, I can probably add more.)
No magnemite? Fine, take Cpt. Qwark the male Poliwrath. It has a huge ego, so it may not learn any moves over 99 base power (it's obviously way too powerful and heroic to use powerful moves :P). Also, since he is a complete idiot, he doesn't know how to hold an item other than his beloved Wave Incense, and he doesn't know how to use healing items.