Hearthpwn

This is the deck I used to defeat the Heroic Four Horsemen encounter. First - I would like to note that it is suboptimal as I do not have Vaporize which is quite crucial in this encounter. However, it does work, though it might require several attempts.

Several notes on card choices and encounter specifics:

You CANNOT use Doomsayer for this particular boss as it is immediately destroyed by Kel'Thuzad. Baron will usually coin out weapon on his second turn, thus keeping Acidic Swamp Ooze while mulliganing is crucial. It will save you at least 8 points of damage and will give you a breather for the first turns. You should also try to obtain your Frost Nova and Ice Lances so you can stall and inflict damage. Also if you don't get the frost spells keep the Fireball - you will most likely kill of at least one of the knights on turn 4 with it. It is important to note that your opponent has only spells at his disposal, so most likely whatever you play will be removed. He uses Repentance and Redemption with priority, so most likely if he has a Paladin secret equipped that will be it. Also other spells he casts include: Frostbolt, Soulfire, Shadow Word: Pain, Shadow Word: Death and Consecration.

Use your Duplicate on either Spectral Knight or Maexxna. Both options allow you to trade very well - Spectral Knight being the better choice as he cannot be targeted by hero spells which is all your opponent has. Maexxna usually gets Shadow Word: Pain-ed, so its basically RNG whether she survives or not.

Stormwind Knight is a decent charger which can help you finish off either a Redemption return if you have two targets for your hero power or a badly damaged knight. 

It is best if you use Bloodmage Thalnos with Cone of Cold or Frostbolt/Ice Lance combo. It also works very well if you have 6 mana and cast a 7 damage Fireball.

If you can - replace Defender of Argus with a second Ice Block and the Duplicate with a Vaporize. Also use Harrison Jones if you have it at your disposal.

Kirin Tor Mage will allow you to place a minion and also cast a free secret, so it is an awesome card for this particular encounter. Generally 4 attack minions are ok as Baron Rivendare has a lot of priest removals.