The Normal Types
There are many normal types that are fast and that's a good thing because Normal Types are the most neutral Pokemon in the game. The Normal types don't launch any super effective moves, but they're only vulnerable to Fighting type moves. Many Normal types can learn Thunderbolt, Ice Beam, Bite and Fighting type moves. Some Normal Types can even learn Surf, so Normal types will give your opponent surprises.(Flying types are in the flying section)
Rattata may not seem like much, but Rattata is very fast and will evolve into Raticate

.You can find Rattata almost anywhere around Pallet Town in Pokemon FireRed/LeafGreen so adding Rattata to your team won't be a challenge. Raticate can learn Hyper Fang, which is a strong move.
Clefairy are rare and can be found in Mt. Moon, but Clefairy can evolve at any level with a moon stone into Clefable. Clefable can use Metronome so you never know what attack you'll launch. Sometimes Clefable can suddenly use Recover at a very tight situation.
Jigglypuff can be found between Mt. Moon and Pewter City. Jigglypuff can use Sing and won't know too many attacking moves when you catch it. But if you train it for a while, it can learn Doubleslap and can evolve into Wigglytuff.
If you've seen Tyson's Meowth, you know that it can use Thunderbolt. Meowth can give you money with Payday and is easy to catch. You can find many to the north of Vermillion City. Meowth will evolve into Persian
You can find Kangaskhan in the Safari Zone of Pokemon LeafGreen and Pokemon FireRed. Kangaskhan is powerful with moves like Mega Kick and Mega Punch.
Tauros can learn Thrash and is fast. Tauros also has high Attack stats so you can't stop this Pokemon from KOing your Pokemon unless you KO it first because mostly it has Persim Berry with it so it can continue to Thrash. Though Tauros may have lower Defense stats, Tauros almost attacks first, so watch out if your Pokemon's Defense isn't that good.
Girafarig is a Psychic and Normal Type that can learn Crunch and Psychic. Crunch is super effective against Ghost and Psychic types so Girafarig won't have to worry about them. You can find Girafarig in the Safari Zone of Pokemon Ruby/Sapphire/Emerald.
Stantler can learn Extrasensory and will mostly attack first. Stantler can have high special attack or high attack depending on what you prefer. Stantler is most likely available for you to catch in Pokemon LeafGreen/FireRed.
Smeargle is a special Pokemon that can learn Sketch that will copy your opponent's last move. Smeargle can also use Dive and can be found in the Battle Frontier in Pokemon Emerald.
Miltank's Rollout was featured as Goldenrod's Gyom Leader Whitney's favorite move. She used it to KO all three of Ash's Pokemon in the animated series thus winning Ash. Miltank can also use Milk drink enabling it to recover lost HP.
Zigzagoon is found in many places in Pokemon Ruby/Sapphire/Emerald and is a fast Pokemon. Zizagoon has a very handy ability called Pickup and can find valuable items for you as you walk. Zizagoon can also use Surf so it can take you on strolls on the ocean.
Delcatty can learn a wide variety of moves including Shadow Ball, Assist, Covet, Water Pulse, Thunderbolt, Ice Beam and Double-Edge. You can get one by using a Moon Stone on a Skitty which can be traded for a Pikachu in Fortree City in Pokemon Ruby/Sapphire. Skitty can also be found in the grasses by Rustburo City, but is very rare. Delcatty can also be snagged from Cipher Admin Lovrina in Pokemon XD.
Zangoose has very high attack and speed so it has very high capabilities of KOing many of your foe's Pokemon. You can find one only in Pokemon Ruby by Lanette's house(which is to the west of Fallarbor Town).
Castform is a Pokemon you can get for free in the Weather Institute after you beat Team Aqua(Pokemon Sapphire/Emerald) or Team Magma(Pokemon Ruby). Castform can also learn a wide variety of moves like Ice Beam.