Have all sixteen badges now.
For Koga I used Pluck on most of his team. Combined with Faint attack for Crobat's Double Team. Taunt was also useful here. So go my precious Murkrow ^^ Thyplosion for Foretress, though.
For Bruno it was pluck again, combined with Flamethrower and a little touch of Earthquake if it was neccesairy.
When I finished the E4, I dumped all but Thyplosion and Mamoswine and added Vespiquen and Kabutops. Rock weakness aloha, but I didn't really seem to bother me much ingame. All at level 60, just before Mt.Silver enterance, saved, and started a new game on Heartgold