Brock: Gra.ss and water types are the best. If you chose Bulbasaur or Squirtle, the battle should be a breeze. If you didn't, use Mankey's fighting attacks. You can also use Charmander when it learns Metal Claw (But be alarmed! Rock-types are strong against Charmander!)
Misty: Use Electric types or gra.ss types against her. If you didn't get Pikachu by the time you reached Cerulean City and you don't have Bulbasaur, go north (Beat your rival first) and catch an Oddish or Bellsprout (Depending on if you're playing FireRed or LeafGreen)
Lt. Surge: Ground-types like Sandshrew (If you're playing FireRed, use Diglett) or at least busted out the TM Dig you got earlier, you should be able to unplug him.
Erika: The best would be to use Fire or Flying types like Charizard (If you chose Squirtle or Bulbasaur then bust out Vulpix, Growlithe, Pidgeotto, Spearow etc.)
Koga: Psychic-types like Kadabra (Or at least a Venomoth's confusion) should be able to KO all his Pokemon.
Sabrina: Bring a rock/flying/fire/psychic type such as Golem, Pidgeot, Charizard or Alakazam for the Venomoth and a bug type like Beedrill for Sabrina (You could also use a dark-type attack since you can't get dark pokemon yet).
Blaine: Water, Rock or Ground types are best. Bring an Onix, Golem, or any other rock/ground Pokemon. By now you should have the Super Rod to get a LOAD of Water-types to go against Blaine. If you chose Blastoise, you should DESTROY him!
Last gym leader (I don't want to spoil his name, so Pyro777, if you're reading this, please don't click thumbs down on this cheat): Water-types are best against you-know-who's Pokemon since they can take them all out, especially the Rhyhorns. Use the load of Water-types I mentioned earlier. If you chose Blastoise, you'll DESTROY him!