Hearthpwn

This is the deck I used to kill Loatheb Heroic Mode.

Make sure to upvote if you found this deck helpful and you've used it to successfully defeat him!

Reminder

1. It will take you a few tries just to get the idea of the strategy + the starting hand/mulligan itself.
2. Once you do understand the idea of the strategy and have the good beginning hand/mulligan its more of a matter of RNG than anything else.
3. Even though its RNG based, you will need good or the right answers at the right times, and never trade in any minion above 2+ Health. Once you do get good RNG, and follow my steps, Loatheb should be a piece of cake.
4. It will take a few to many tries depending on your luck after your have done #1, but don't be discouraged, you can do it. Just keep trying and you will succeed! :) 

Mulligan

Begin the game by mulliganing for Elven Archers, Hunter's Marks, Stonetusk Boars, Arcane Shot, or Freezing Trap.

Strategy

1. You must have either Hunter's Mark + Elven Archer/Stonetusk Boar/Arcane Shot or Freezing Trap before you even begin the match itself, otherwise insta concede till you get either of those combo's in your beginning hand.
2. Once you have #1 done, use either the Hunter's Mark Combo Wombo or the Freezing Trap to take care of the Fen Creeper at the beginning of the match.
3. After you have done #2 from this point onward your only objective is to go for the face/flood the board with your minions.
4. As you flood the board with minions, if Loatheb places another taunt use a Freezing Trap or Hunter's Mark combo to efficiently clear it.
5. When you flood the board and avoid trading with Loatheb, you prompt him to use Deathbloom to clear your minions. He will also use Sporeburst to deal 1 AoE damage per spell and flood the board with spores.
6. Once he has flooded the board with 3 spores or such, and you have flooded your board to the best of your abilities, but have in no way taunted a minion or proved a threat allowing Loatheb to go for face with his minions, ensure you survive the following turn and put up 1 Explosive Trap thus ensuring that on Loatheb's following turn not only do you survive but also pop all the spores, thus allowing all your minions to get +8 Attack Per Spore and if 2 or 3+ minions survived that turn and no taunts have been placed by Loatheb, you automatically win the following turn with your board. Plus Hero Power if needed.
7. There will be times where he will place taunts and other such shenanigans, remember to use what's available to to clear the taunt or such with "MINIMAL BOARD LOSS". Be weary of your minions health, always insuring they are 1 above the Sporeburst damage, especially when you setting up for the next turn kill. You wouldn't want Loatheb to place a Unstable Ghoul thus killing your board the next turn.
8. Use Freezing Trap if you don't have hard removal, and just skip your turn, allowing Loatheb to proc the trap with taunts.
9. Never lose board presence, always use your spells to get through whatever it is that needs to be taken down. Reason for the crazy amount of spells, and they prove quite effective in the match.
10. If you need to clear a taunt and have no way to do so effectively use your 1 Health Minions to do so, as they don't survive the Sporeburst AoE thus they are more of a liability than guaranteed damage like your other minions.

Card Knowledge

Deadly Shot - Its in the deck to ensure for multiple ways to bypass taunt minions or other threads as an auto clear if its the only alive.
Earthen Ring Farseer - Its in  the deck to ensure it survives the Sporeburst AoE damage, +3 Heal to you basically giving you an extra turn.
Unleash the Hounds - Its in the deck to give you easy "Board Flooding" potential to prompt Loatheb to use Deathbloom/Sporeburst in order for you to set up for combo, also allows for uber damage is you happen to pop spores and hounds lived for the turn.
Arcane Shot - Its in the deck as an added measure for killing taunts, spores, or other minions with Hunter's Mark combo, or with the spell itself. It gives you great flexibility.
Multi-Shot - Its in the deck to give some sort of AoE clear, especially for Flesheating Ghoul, and Shade of Naxxramas.
Houndmaster - Its in the deck because due to the taunt potential with might go nicely with an unleash the hounds combo.
Tundra Rhino - Its in the deck due to its instant charge ability, and also as bait for the Deathbloom spell.
Animal Companion - Its in the deck due to all 3 potential beasts which work really well with the overall strategy.