Hearthpwn

This is the deck I just used to 1-shot Majordomo Executus on Heroic. It's freeze mage but with the unlimited fireballs combo. I was a bit surprised to see Ragnaros with 30 hp and 30 armor when he was summoned, but it didn't matter to me because I was still chain casting fireballs. In my first attempt on normal mode with Paladin I discovered he had molten giants. This is what led me to this strategy. There is no reason to do any damage to his face until the unlimited fireballs are ready to go, as this locks out 1/3 of his deck.

The deck works like freeze mage, just use your spells to control and wipe the board. Make sure you get your card drawing mechanics and mad scientists early. Majordomo seems to like controlling your board. He traded and lava bolted my first wave of apprentices instead of going on the aggressive, which may have helped me win.

The combo is achieved by playing double sorcerer's apprentice, casting Echo of Medivh, playing the two apprentices you just copied, and then playing the second echo. When you have done this and have Archmage Antonidas in hand, play Emperor Thaurissan. If you have Ice Block up at this point, you've won. Play your reduced cost minions and chain fireballs until the game is over.

The reason I included clockwork gnome in the deck is for a guaranteed free spell to start casting fireballs but there are many other cards you could use for this purpose, so that can be replaced easily.