Well, I'm not gonna make a full-on moveset like everyone else does, just a list. :3
In no particular order...
Togepi
Evolves into Togekiss, has a very unique movepool if you include TMs.
Gyarados
Don't underestimate adding a Magikarp evolution to your party. It has awesome stats. Watch out for it's x4 weakness to Electric though.
Dratini
Use this as a last resort. Dratini can only really be found at Level 5, in Blackthorn, and can be incredibly hard to level up into a Dragonite.
Pidgey
I can't say anything positive about this Pokemon, since it can be annoying when it needs to be. However, it's another good last resort.
Skarmory
This is probably a good option since it can deflect you from those annoying yet extremely Electric-type moves and Steel-type moves that make you faint very quickly. Found pretty late in the game, though.
Hoothoot
Again, another last resort. Noctowl doesn't have the best of stats, but has pretty high Sp. Def if you like bulky Pokemon. xD
Zubat
These pesky bats can be very helpful when it becomes a Crobat. Crobat has 130 Speed, and 90 Attack. So it has just-over-decent stats, I guess.
Some of these Pokemon can appear late in the game, so I'd recommend keeping a(n) HM Slave for Fly. Like Pidgey or Hoothoot, whenever you can find one.
My real suggestion is Togepi or Gyarados, since both appear early in the game and when it comes to battling they can be pretty damn good.
Oh well, hope I helped. :)
