Hearthpwn

It's expensive but it works.
Please, rate this deck if it helped you :)

Strategy

This deck consists basicaly in gain the board control making use of taunts and KT.
Keep in mind he will use 2x Twisting Nether, but you can win even if he clears your board with KT on it.
If your KT got killed, you can easily go to fatigue with this deck and win, just make a good use of:
Poison Seeds + Baron Geddon / Tree of Life / Alexstrasza / Deathwing.

Mulligan

Try to get the best legendarys to give you advantage on the start, like:
Sneed's Old Shredder (since he usually uses Drakkisath's Command at the start), Cenarius, Ragnaros the Firelord and Foe Reaper 4000.

Budget Version

If you dont have one legendary or another you can swap for:
Sunwalker, Lord of the Arena, Frost Elemental, Ravenholdt Assassin, Faceless Manipulator, War Golem, Sea Giant, Core Hound, Clockwork Giant, or any other big minion.

I tried a budget version with 2x Mind Control Tech and 1x Savage Roar (instead of Poison Seeds and Tree of Life) worked very well.

If you dont have Baron Geddon take off 1x Poison Seeds and put Starfall

Taunt givers are viable too because of KT: Dark Wispers and Mark of the Wild.

The "2 turn combo" Onyxia+Savage Roar its a pretty good finisher too, and also have a nice synergy with Poison Seeds.

I had a lot of bad luck (KT and good board cleared 2 times) buy, even so, i was able to beat him on the first try.
Hope it helps.