I never have problems with the gym leaders. I'll kill there Pokemon in One-hit KO. This is how I do it.
-Brock- If I choose Bulbasaur as my starter, I just have to use a Vine Whip and he is dead. If I choose Charmander, however, I'll catch a Mankey to cream him. (I usually try to get my starter to evolve before the first gym battle)
-Misty- I'll just use Razor Leaf with my Ivysaur and they are dead, or I get a Pikachu and train him until he knows Thunderbolt.
-Lt. Surge- By far one of the easiest. Why do you thing the Diglett Cave is there? I'll go catch a Diglett, train him until he is a Dugtrio and "Dig" his Electrics into a grave.
-Erika- Charmeleon/Chairzard or a Pidgeotto/Pidgeot. Grass-types are weak against Fire and Flying, so if you have a Fire-type, use Flamethrower, or if you have a Flying type, use Wing Attack. If you dont have any of these types, go to the patch of grass just before you go into Celadon and catch a Growlithe.
-Koga- Use a Kadabra/Alakazam, or Mr. Mime if you traded for one. One Psychic can kill his pokemon, you dont even have to use Calm Mind.
-Sabrina- Get yourself a Snorlax or a Gyrados that knows Bite. Snorlax has some great Sp. Def. and powerful Physical attacks. Psychic types have really low Defense.
-Blaine- Visit Seafoam and catch a Golduck/Slowbro, or if you have Blastoise is good too. Also bring along a Rock/Ground type for good measure, he wont stand a chance.
-Giovanni- Water-type attacks, and Psychic against his Nidoking and Nidoqueen.
The gym battles are very east as long as you think about the types that you have to face before hand. If you want some help here is a nice sample team:
Primeape
Raichu
Dugtrio
Pidgeot
Alakazam
Gyrados