Hearthpwn

This deck can be used to beat the Four Horseman on Heroic mode.

The strategy: The cards in this deck fall into one of three categories. The goal is to silence the three Horseman minions (or kill using Shadow Word: Pain), use Taunt minions and the healing hero power to stall long enough to silence the minions, and get enough burst to deal 14 damage in one or two turns.
1. Silence
2. Stall
3. Burst

Silence: These cards will neutralize the horseman minions. Even though you do not kill the minions in most situations, the Stall cards will help you take the constant stream of 6-8 damage. Silence, Shadow Word: Pain, Ironbeak Owl, Mass Dispel, and Cabal Shadow Priest all fall into this category, even though not all of them silence. Cabal Shadow Priest is probably the best card to use in this category as it gives you more stall because the minion will give you immunity. I ran one Cabal because too many high cost cards slows the deck down. Usually the game will be over by turn five or six.

Stall: These cards will soak up damage to ensure you last until turn six. Acidic Swamp Ooze, Shieldbearer, Unstable Ghoul, Deathlord, Mogu'shan Warden are all in this category. Acidic Swamp Ooze is used to remove his weapon when he equips it, which can potentially prevent 4 damage if you play it after he's only attacked once with the weapon. Deathlord is the best. Since the heroic Horseman deck runs no other minions, this is a cheap 3 cost 2/8 card. It usually soak up a full turns' worth of damage, unless a Repentance is in play.

Burst: These cards will let you deal 14 damage in one or two turns once you've taken the Horseman minions out of the picture. Holy Smite, Mind Blast, Bluegill Warrior, Wolfrider, Leeroy Jenkins, Holy Fire, and Reckless Rocketeer are all in this category. 

The Mulligan: When choosing which cards to mill, try to get a good mix of all three categories of cards. One of each is your best bet. If you pull Mass Dispel, Leeroy Jenkins, Deathlord, or Cabal Shadow Priest, I'd recommend not replacing those cards as they're some of the best in the deck to deal with the Four Horseman.