In case anyone else struggles too: I changed my team to:
- Nidoking Lvl 72 w Poison Jab, Toxic Spikes, Sludge Bomb, Sucker Punch
- Drapion Lvl 72 w Toxic, Toxic Spikes, Crunch, Bug Bite (or was it Bug Buzz?)
- something else (iirc Masquerain Lvl 72 w Discharge, Air Cut, Ice Beam, Bug Buzz)
I only needed the first two, tho. And some potions to fix the Nidoking up. Actually this team worked on my first attempt with these three! I was surprised and happy by that, too.
The cursed Zangoose was OHKO by Aelita's Hawlucha :3 and ohhh boy was that satisfying
/Addition:
Audino trainers weren't necessary; my Nidoking was mostly up to level, so it only took some Exp. candies.
I didn't set up Toxic Spikes, just Poison Jab'ed the mons, healed the Nidoking as necessary. At some point it got knocked out, so it was up to Drapion. Worked surprisingly sweet!