Hearthpwn

It's pretty obvious how you play this. I've only just started testing it on the ladder, but it had enough oomph to beat a midrange paladin at rank 4, so it can't be that bad. 

There's some decent overlap between C'Thun and the quest in Twin Empreror Vek'lor and the Crazed Worshipper (which was never played in straight C'Thun warrior). Twilight Geomancer is probably still just plain bad, but I'm trying it out. I can't imagine what I'd need C'Thun to have taunt for; by the time you can play C'Thun on turn 10 you're likely dead, and he should clear the board in any case but it would be nice to make it work. Plus it gives a turn 2 play vs Pirate Aggro, and the psychological impact - taunt AND C'Thun - might make an opponent wobble. 

Apart from than, it's just a deck full of value. Could probably use more draw - the Geomancer for another Acolyte. I might be tempted to make room for a Ghoul; probably lose either a Dirty Rat or an Alley Armorsmith. A couple of Ancient Shieldbearers would be nice too, especially to build armour for Shield Slam after you've turned in the quest, but it's hard to know what to cut for them. 

Mulligan for: Win Axe, Geomancer, Disciple of C'Thun, Stonehill Defender.

If you know your enemy curves super low or is combo (a rogue, basically) you could keep a Dirty Rat too. If it's a rogue also keep a Brawl. They'll probably have finished their stupid poxy quest by turn 5.