1. Dragonite - Dratini from Dragon's den (after beating Clair and answering a few questions). If you need one, Dragonite will serve fabulously as a HM slave.
Dragonite
Ability: Inner Focus
- Thunder Wave/ Dragon Dance
- Outrage/ Dragon Claw
- Aqua Tail
- Extreme Speed (Dragon Den Dratini)
Dragon Claw is better than Outrage, if only because it doesn't confuse you; you can get the TM as first prize from the Goldenrod Lottery (top floor of the department store) on a Sunday, so I would try for that.
2. Zubat - get a Zubat... anywhere, really. Zubats are a pain to level up early on, but after that Crobats make a nice addition to a team. Shame Acrobatics came in at Gen V.
Crobat
Ability: Inner Focus
- Wing Attack/ Pluck
- Mean Look
- Bite
- Roost/ Fly
Mean Look will be absolutely brilliant for trapping annoyances like Raikou and Entei.
3. Swellow - headbutt trees in Cherry Grove for a Taillow. Frail, but has the benefit of Guts and good speed.
Swellow
Ability: Guts
- Quick Attack
- Aerial Ace
- Return/ Facade
- Fly
I also would recommend Togekiss, but while it's a good Pokemon, you cannot get a Shiny Stone to evolve Togetic until late in the game.