Proposing Onix for Medium Tier because it's fantastic start, good overall help along the game, and defensive phyisical stats that are equivalent to the best physical walls of the game. He can deal great damage with Screech + Rock Throw on few turns, too.
If he's able to evolve via traiding, then it should be placed on High or Top Tier, and the comments should have a lot of changes (specially with the gym's stuff). On the HIDE I'll put the version with traiding aplied.
Availability: Earlier and easy, you can trade one for a Bellsprout on Violet City.
Gyms that it fares well against: Wins alone against Falkner, Bugsy, Whitney, and Lt. Surge without problem, and is helpful against Morty (needs the Mud-Slap or Dig TM), Jasmine (same as before), Koga, Karen, Janine, Blaine, and Red (good against Pikachu, Snorlax, and Charizard).
Additional Comments: He's better than Geodude before it evolves, and is somewhat similar to Graveler, except because Onix prefer to deal damage with Bind + Sandstorm and wall the enemy while he's Screeching it for others or himself, too. Also, he can handle and survive to any random Self-Destruct and Explosion, and give you time for revive/heal him's partners on mid battle. He will not sweep any time soon, but he can easy handle a good number of trainers and gyms alone. Also, he's a in-game trade, so, he'll win experience faster and will have better levels with less effort, and if trades are counting, Steelix is just awesome.
Availability: Earlier and easy as Onix, you can trade one for a Bellsprout on Violet City.
Stats: Adove avarage.
Gyms that it fares well against: Wins alone against Falkner, Bugsy, Whitney, Morty (once evolved), Jasmine, Pryce, Will, Koga, Lt. Surge, Sabrina, Erika, and Janine, and is helpful against Red's Pikachu and Snorlax.
Additional Comments: While he's Onix, he will be superior to Geodude, and somewhat similar to Graveler, but taking more turns to deal the same damage (but taking less damage from the enemy as well), but once it evolves; thing he can do before Morty with the Metal Coat from a wild Magnemite - but they had only 3% chance to have it -, (or keep it as Onix until aboard the S.S Aqua, somewhat late, sadly), he'll crush and destroy everything on the game that doesn't have Fire or Water attacks, and even then, he can deal huge damage or use support moves before failing or switching-out against them.