Here's a team I like a lot. No trading required:
It's a Charizard, you know what it does. Aerial Ace won't get tons of use, but it's nice to be able to hit Fighting types without wasting a turn on Fly. You could swap Slash for Dragon Claw, I just didn't want to spend the TM and I like Slash's critical hit rate. Dragon Claw gives better coverage (nothing resists both Fire and Dragon) and comes off Charizard's generally higher Special Attack, but Slash isn't far behind, leaving you vulnerable only to Rock types, which Charizard has no business fighting anyway. Dragon Claw will only give you super effective damage against Lance, and Ice moves are a better choice there. Fly is self-explanatory.
Exeggutor (hold Leftovers - found under each Snorlax)
-Giga Drain (use a couple PP Ups on this)
Exeggutor has a lot more staying power than you might think, especially with Leftovers and the draining moves. Sleep Powder is better than Hypnosis, but it might not be worth sticking with Exeggcute until level 37. Swapping out Sleep Powder for Toxic is justifiable, but sleep is more useful for catching things and anything can learn Toxic. Other Grass-types have their uses, but Exeggutor is the strongest overall; Psychic is a much better secondary type than Poison. This gives you a good Psychic-type without having to trade for Alakazam.
Lapras is tough and a great special attacker. Pure electric types are pretty weak and non-versatile in this game (other than Zapdos, and I try to avoid legendaries in-game), so I prefer to stick a good Electric attack on something else. Lapras is excellent in this role, because it resists other water types and can hit them hard with Thunder/Thunderbolt. Surf and Ice Beam are obviously strong attacks that get type bonuses, and the last slot can be for a utility/support move or any HM you're lacking elsewhere - Lapras can learn Strength and Rock Smash too. Lapras with this set will be EXTREMELY useful against the Elite Four.
Snorlax (hold Leftovers - can be found under each Snorlax)
Snorlax is a strong Pokemon, and with Rest and Leftovers he'll be very hard to kill. Body Slam hits hard and might paralyze, helping with Snorlax's abysmal speed (and this team is fairly slow in general). Return is a stronger option if you can paralyze another way. Shadow Ball, surprisingly, is a physical move in these games. This makes Snorlax incredibly effective against both Psychics and Ghosts, as he has a really high Special Defense and HP to soak up their attacks, doesn't care much about falling asleep, and hits them back with a super-effective Shadow Ball. He's a great counter to your rival's Alakazam, Agatha's ghosts, and Sabrina's gym, while being a strong counter to just about anything without Fighting moves. Either Ability is good; I think Thick Fat is more useful than Immunity but it's up to preference.
Toxic is not really recommended here as it makes you vulnerable while asleep, but it's always an option if you need to wear something down. Counter is also probably not the best choice, but Snorlax has the HP to make it deadly in the right situation.
Rhydon (hold Quick Claw)
Rhydon is a great physical tank, and counters all Electric-types, along with Normal and most Flying-types. Earthquake is ridiculously strong in general coming off Rhydon's high Attack, and Rock Slide takes care of Flying Pokemon that are immune to EQ. Focus Punch is somewhat hard to use, but will hit Normals extremely hard. Don't bother with Brick Break; even when super effective it's not any stronger than EQ. Double-Edge deserves mention if your Rhydon has the Rock Head ability, which eliminates Double-Edge's high recoil. Again, though, it has limited use as compared to Earthquake or a super-effective Rock Slide. Megahorn is a very strong Bug-type move, giving you a nice way to deal with Psychics (and Grass-types, but Rhydon shouldn't stay in against them) but Rhydon doesn't get it until well past level 60, and Snorlax is a better way to deal with them anyway as it can take special attacks much better. You can safely make the last two moves HM's, but if Cut is on something else you can go for something more interesting.
This leaves you with one more slot for something of your choosing! An Electric or Fighting-type is a good choice, but they don't really give you much the above team doesn't. Jolteon, or Electabuzz if you're playing Fire Red, are the strongest options (not counting Zapdos), but neither can learn much besides Electric moves. They are fast, though, and can paralyze things with Thunder Wave. They also can learn Flash. A Pikachu/Raichu is useful until you can get Lapras, but is outclassed by Jolteon and Electabuzz as a dedicated Electric type.
The best Fighting types are Hitmonlee and Primeape, unless you can trade for Machamp. I typically use a Mankey/Primeape for the first part of the game, but it's really not necessary once you get Rhyhorn, which is much more durable, resists Normal (as well as Flying), and hits harder in general. Literally the only thing a Fighting type has over Rhydon is STAB fighting moves, which isn't really enough to justify a party slot.
Dragonite is also a strong option here, with a versatile movepool to fill any niches you want, and the stats to do almost anything. However, it's fairly tedious to raise one. Nidoking/Nidoqueen are more easily obtained, and also have very wide movepools. They are also good Ground-types until you can get Rhyhorn, though they face competition from Diglett for that role. They're sturdier than Diglett and more versatile, but slower.
A more support/utility type Pokemon is also an option. Something with a lot of status moves, perhaps, or something good at catching other Pokemon. Scyther (Fire Red only) and Farfetch'd can learn False Swipe, which will always leave the enemy with at least 1 HP, allowing you to whittle down something's health without worry. Scyther is also strong and fast in its own right, though it can't learn that many moves.
Otherwise, you can use this as a slot for a general HM slave. The core I listed lacks Flash, and won't have Cut until very late (only Rhydon can learn it, not Rhyhorn) so you'll need something to use those moves. Meowth is a good one for those if you're on Leaf Green, and comes with the bonus of the Pickup ability. Free items!