@Its a Random, this isn't the most creative challenge, but you'll have to be very creative to beat it :P
Take a Rattata named Zen. This little Rattata wants to fight and win. It constantly seeks to prove itself, not only as a strong fighter, but as a versatile fighter. Thus, it will put itself in the most difficult situations to prove, both to you and to itself, that it can handle anything. Zen must solo at least 1 Pokemon in EVERY gym, with restrictions.
Falkner: No STAB
Bugsy: No STAB
Whitney: No level up moves
Morty: No Dark type moves
Chuck: No STAB
Jasmine: No Dig
Pryce: No STAB or moves that Zen has used in battle before the match with Pryce
Clair: No moves with more then 60 base power
It also refuses to evolve into Raticate until after soloing one of Morty's Pokemon. After doing so well, Zen will finally have the confidence to stop giving itself such ridiculous challenges. However, its fighting spirit is still burning strong, and it must continue to solo at least 1 Pokemon from each E4 member, the Champion, each gym leader in Kanto, and ultimately Red.
Have fun!
EDIT: Meh :( I read the rules, but got so focused on making the restrictions that I forgot about it. Sorry