You should catch a Cubone. Not because it's powerful, but because it can be traded for a Machamp (well, a Machoke, but it evolves upon trading).
Machamp is a powerful physical attacker and can take a hit too, and unless you have 2 Game Boys and a link cable, there's no other way to get it.