Empoleon, I got to about 79 with a team using a (non-Trick) Metagross lead. You'll want a Ground immunity BADLY, since it will be annoying as hell when the following situation keeps happening:
Opponent's lead (faster Pokemon) used Surf/Thunderbolt/Shadow Ball/some other move that does neutral damage!
Metagross used Earthquake/Meteor Mash!
Metagross used Bullet Punch! Opponent's lead fainted!
Opponent sent in Pinsir/Garchomp/Gyarados/one of a million other Pokemon that are faster than Metagross and carry Earthquake.
Opponent's Pokemon used Earthquake! Metagross fainted!
Starmie and Garchomp are fantastic backup, but at some point, you'll run into a situation where the opponent can take both of them out without a full team. I don't think that team will get too far past battle 49 (maybe somewhere in the 60s?) because there are some Pokemon that just manage to annoy the hell out of all-out attacking teams. Some examples are the Latis (too fast, and generally too bulky to take out with a single Ice Beam, Aerodactyl (you'll come to hate the one carrying Thunder Fang and Ice Fang, and the Choice Band set hits really hard too), and teams of Water-types. Water-types in particular are a problem, since all Metagross can do against a lot of them is explode, and the Water/Grounds (and Lanturn) are generally bulky enough to take a hit from Starmie and mess it up with Earthquake.