I found a pretty simple way, using only rentals.
3.pokemon super effective against gym leader or counters their strategy (ex. using safeguard against Erika)
Use wobuffet to counter or mirror coat the foe, taking out at least one, maybe 2 if you can get in destiny bond. If one particular pokemon gives you trouble, use haunter and destiny bond another, then just sweep their 3rd pokemon with a super effective hit. This worked really well for me, beating almost every gym leader on the 1st try.