Well, the only two trainers I've had any difficulty were, were Red and after 16 badges Lance. Lance because I ran out of revives and I barely made it through with my Gyarados. Red was hard, but not if you use a good strategy.
I used Jolteon to paralyze it. Volt Absorb makes all electric moves useless, so Red uses Quick Attack or Iron Tail. (Both do a hell of a lot tho =\). Switches into my Machoke and EQ'd it for the KO. Rest of it, (except for Snorlax >=[ It knocked out Gyarados with Giga Impact and I had to Cross Chop it, then set up my DD's after reviving Gyarados... ugh... ) was just playing to the weaknesses. Gyarados is a beast - DDx3 and Waterfall/Icefang - instant KO on most of his Pokes.
My team was a lv. 60 Typhlosion (Eruption, Flamethrower, Shadow Claw, Cut), lv. 60 Gyarados (Waterfall, Dragon Dance, Surf, Ice Fang), lv. 58 Crobat (Bite, Air Slash, Fly, Confuse Ray), lv. 59 Machoke (Earthquake, Cross Chop, Strength, Rock Climb) lv. 60 Gengar (Psychic, Hypnosis, Dream Eater, Dark Pulse) lv.59 Jolteon (Thunder Wave, Thunder, Quick Attack, Shadow Ball)
-obviously my move sets need work xD-
None of them were EV trained either =]