Hearthpwn

I originally came up with this deck from a regular Control Warrior.

The Core

Realising the value that Kel'Thuzad would gain in this deck, especially when Faceless'ing him, I added him. Obviously, due to Majordomo having 6+ Molten Giants (I found out the hard way, lol) and Ragnaros' ability, big minions that can trade efficiently with smaller ones and soak 1-2 hits (8+ hp or Divine Shield) are extremely important. Also, you DO NOT want him flooding the board with his Giants, due to obvious reasons. It's better to have a KT and a couple big minions to control it slowly while killing his dudes and wait for your Gruul to grow and OTK him than try your luck against Ragnaros' hero power.

Early Game + Mulligan

Majordomo plays realtively small minions (Imps 3/2) and his hero power (3/3), so mulligan for weapons, Armorsmiths + Cruel Taskmasters and Earthen Ring Farseer. You WILL take damage, but don't be afraid. Your hero power and Earthen Rings + Shield Block/Shieldmaiden after you stabilize, will be generating so much armor you can actually go fatigue war with him. Also, having 10-15 health enables the Molten Giants, which also help you stabilize and take board control.

Mid Game

You want to draw into Chillwind Yetis and Stalagg so they can draw your opponent's removal to them. Don't worry, they're there exactly for that. You want to start taking board control with a Giant, Shield Maiden, Maexxna.

DO NOT rush him, DO NOT try to bring him below 20 hp until you reach YOUR late game. If by turn 10 you haven't drawn Kel'Thuzad, it's better to concede and try again, rather than keep on insisting and throwing big minions into his endless supply of small dudes, even if it means you're trading 3-4 to 1.

 Late Game

The late game is based on drawing and playing Kel'Thuzad + Faceless Manipulator before you run out of Molten Giants/Gruul (good at removing Majordomo's Giants) and still having at least 1 Sludge Belcher (it's also ok if you lose both, but they're better at removing the small hero power dudes).

Possible substitutions

Gruul -> MAYBE Shade of Naxxramas, but since their scaling is completely different, they might work differently in this deck. With Gruul and a couple of big minions, I literally OTK Majordomo (half hp, no armor) and Ragnaros (75-80 damage in one turn), with Gruul being at 45/35 by fatigue.

Alexstrasza, Dr. Boom, Sylvanas Windrunner -> Any BIG minion that can trade rather efficiently against midrange ones, like Boulderfist Ogre, Sunwalker, Lord of the Arena, War Golem, 2nd Force-Tank MAX.

*Alexstrasza, as far as I remember, works with both Majordomo and Ragnaros.*Removed Ragnaros, after some testing, and realising that a 2nd Force-Tank MAX would be more reliable, and since you often don't want to push Majordomo too far with this deck, the Tank is more reliable earlier in the game.

I also would have to try these subs, since all the tries I've done were around the Giants/Gruul and KT + Faceless, but I believe they would work.