Turn 1: Argent Squire, Possessed Villager or Dragon Egg on the left side of Red Portal to prevent him of making 16 dmg. He usually hit the minion and nothing else on first turn, wasting 7 dmg.
Turn 2: Goldshire Footman, Shieldbearer, Voidwalker, or Annoy-o-Tron on the Right side of Blue Portal preventing him to do anything.
From then, you must do the usual of Zoo flooding the board. The best scenario is using Darkshire Councilman with Windfury and Annoy-o-Tron on the Right, since his shield gives you 2 free turns even after he uses Nether Breath.
Just remember to continue replacing Taunts on Right and buffing anything with Windfury.
I did it at the first try, so, don't know if there are better ways to do it, so far, this works.