That is a tough one, koff~
For battles with trainers: Toxic Spikes and Sludge Wave.
Individually? I love Acid Spray. It's absolutely lethal when paired to Muk and it's minimize. Can't hit Muk, and you keep dying from a harshly lowered Special Defense stat. Couple Muk with Flamethrower (Or fireblast) and another special move (Preferably shadowball) and you're golden. If you're feeling really mean, put a Metronome on Muk and put Substitute on it. Minimize yourself entirely, then Substitute, and then just Acid Spray to victory! What? A steel Pokemon? Just hose that pesky "I'm better than you 'cause I can't get poisoned" ninny down with your Flamethrower and they'll be weeping all the way to the Pokecenter. It still irks me that Koffing can't learn Acid Spray, but what are you going to do?
Muk would also make a great wall that they can't get across. Minimize, Substitute, Protect, and Poison Jab. Alternatively, you can do the same with Garboder and Weezing with Double Team, but it takes longer. What's nice about Weezing is that it's immune to ground type moves and you can pair it with Double team, Smokescreen, Will-O-Wisp and Protect (or Smog/Poison Gas)
Also, Mega Evolutions for the pollution trio. This needs to happen. Mega Muk, Mega Weezing, and Mega Garboder. Mega Muk would gain the Infiltrator ability due to it's slimy nature and it's Attack, Hp and Speed stats would be boosted.
Mega Weezing is now Poison/Dark type and Boosts it's Attack, Speccial Attack and its Special Defense.
Mega Garboder now has Furcoat. Yeah. Why? Just 'Cause. You know that mold that grows on garbage and how it gets all fuzzy? That's why I went with that ability. Furcoat, ergo, 'Moldcoat'. Hp, Defense and Special Defense is increased. Nasty, koffi~