All credit goes to chakki_hs for making this deck. (http://www.twitch.tv/chakki_hs )
This deck is in my opinion the easiest way to beat Heroic Majordomo. The main goal of this deck is to kill Majordomo and Ragnaros in 1 turn. This can be done by dropping down the 2 Shade of Naxxramas as early as possible. Utilise buffs such as Blessing of Kings. Be patient when using your Blessed Champion as this card is vital when it comes to finishing Majordomo.
The reason why we set up to kill him in one turn is to prevent the Molten Giants coming out and just wrecking your board. Warning Ragnaros has 60HP when he comes out!
Mulligan for cards to maintain Board Control such as Shielded Minibot and Muster for Battle. Even cards like Aldor Peacekeeper and Hammer of Wrath can be kept to handle those Hero power minions. Also Quartermaster is a vital card to deal with the Hero power of Majordomo. This card can also be kept in your hand if you have a Muster for Battle.
If you get out your shades early enough this is easy to win. Don't use your Blessing of Wisdom on your shades. Use them on Silver hand Recruits to draw more cards, and thus drawing more combo cards for the shade. If you have Emperor Thaurissan on turn 6, you most likely drop him on the board to make everything cheaper.
So to sum everything up:
- Get Shade of Naxxramas out as early as possible.
- Maintain board control with your early game.
- Use your heals to stay alive.
- Try to buff your shades (if possible) every turn!
- Try to kill him in 1 TURN
If you still have any problems defeating this boss I suggest you check out his Twitch channel to see how he did it. The fight starts around 27:00 Minutes in