I believe Infernape will over Staraptor.
Infernape, in my opinion, could handle most of the Gyms using
Close Combat, Thunder Punch (Move Tutor), Flareblitz (Or reasonable fire move), and this move is up to you. You are able to cover Normal, Flying, Rock, Steel, Ice, Water, Bug, Grass, (Bleh too lazy to list them all)
For the last move, you can use Arial Ace (For Fighting), Feint Attack (For Psycic and Ghost) or U-Turn (For Psycic)
The last move is up to you I suppose. Of course, you can replace Flare Blitz with Flamethrower but you would need to trade for it or get it at the Game Corner. Flamethrower is more reliable because Flare Blitz will wither down some of your health (Unless you can backup with Leftovers, or potions) Best part is, these moves are all physical so yeah.