Dragonite is great late-game, as it learns all its best moves ingame. Agility, Wrap, and Hyper Beam are level-up moves, and Surf is required to complete the game.
Only problem is that it levels up slowly and requires a bit of grinding to be good mid-game.
Even if you can't trade, Kadabra and Haunter are really good on their own. Kabadra learns mostly Psychic moves, but the only Pokemon that resist it are other Psychic types. He also gets Recover, which helps since there is a finite amount of money ingame until you can keep beating the Elite 4. Haunter requires TMs to be good, but they are well used on him.
Dugtrio is also a solid in-game choice. It learns Slash and Earthquake through level-up and has decent stats by RBY standards.
Dodrio gets great level-up dual STABs in Tri Attack and Drill Peck, and it can also serve as a good Fly user for traveling between cities.
Lapras gets good moves through level-up including Ice Beam, Hydro Pump, Body Slam, and Confuse Ray.
I still highly recommend getting a Tauros for ingame play. Earthquake is well used on him, and Strength is a passable move for ingame purposes.
Edit: If you don't mind using legendaries, Zapdos is a great choice. And as many have stated, Snorlax has a great level-up moveset.