I don't have the decks (deleted them after I finished), but I'll list some of the key card choices and overall strategy.
Noth: Freeze + Trap Mage, with all my early game removed. Ice Lance, Frost Bolt, Arcane Explosion, Frost Nova, Counterspell, Ice Barrier, Vaporize, Fireball, Polymorph, Blizzard, Flamestrike and Pyroblast. Also used some late game creatures thrown in although I don't remember which, and a single Doomsayer. I think I might've used Ethereal Arcanist and Kirin Tor Mage. Just control the board and ping away at him until it's safe to play a creature.
Heigan: Priest, with Lightwell/Gargoyle + Divine Spirit to soak up the Hero Power, Anub Eggs for free 4/4s (that get Soulfired every damn time). Circle of Healing, Silence, Smite, Shadow Words (both), Holy Nova, Lightspawn, Shadow Madness and Auchenai Soul Priest. Strategy was to take control of the board and then set up the buffer, and just keep removing things from the field while you chip him down.
Loatheb: Warrior, curve didn't go beyond 4 mana. Warsong Commander, Harvest Golem, Earthen Ring Farseer, Argent Squire, Cruel Taskmaster, Armorsmith, Frothing Breserker and Voodoo Priest for bodies. Cleave, Execute, Slam, Shield Block for spells. Do not use weapons, you absolutely cannot take any amount of extra damage. I had to redo this a bunch of times to get a nutty hand. Basically, you want to use the initial Spore they give you to establish control of the board, and then keep trading while building up your side with bodies and his side with spores while staying ahead of his Hero Power with Armor Up/Shield Block. Once you get a critical mass of Spores, pop as many of them as possible at once and then go for the dome. Should take no more than 2-3 turns, and you'll be cutting it close. Whirlwind for that final push is a possibility, but I didn't try it.
EDIT: Hunter is a possibility for this fight as well, but I had disenchanted all my key Hunter cards for bonus dust so I couldn't put together anything.
The gist of this wing is to:
1) Figure out a counter for the Hero Power
2) Control the board