Hearthpwn

Highlord Omokk is a very difficult fight.  Because one of your minions dies at the start of each of his rounds, and because you have no means of controlling which minion dies, your best bets are to either play single minions that have beneficial deathrattles, or lots of minions so you don't care which one dies.  This deck takes advantage of those two scenarios to first limit the enemy board control, and second fill the board with everlasting Kel'Thuzads.

This is the deck I used to beat Heroic Omokk.  

The gameplan is to survive any way you can until you have both Kel'Thuzad and Reincarnate in your hand.  If you also have Emperor Thaurissan, you'll want to drop him to bring the cost of the combo from 10 to 8 mana.  If you don't have all 3 of those cards by turn 7, you're probably going to lose.  That being said, the cards you want in your starting hand are most likely Mind Control Tech and Exploding Sheep, just to help you survive to turn 8.  Early mind control techs are very helpful as they both act as removal and net you two cards for the price of one.  Try your best to only play cards alongside totems so you have more critters on the board than Omokk's hero power can instantly kill.

Save [hex] for Mogor the Ogre, Ogre Ninjas, or Boulderfist Ogres.

Once you get to turn 6 or 7, and have the three combo cards in your hand, you're all set.  Drop Emperor Thaurissan (even if he'll die immediately), and prepare for awesome on turn 8.  Turn 8 comes along and you're still alive, it's time to play Kel'Thuzad, castReincarnate on him, and prepare for a never ending stream of Kel'Thuzads.

This deck doesn't guarantee a one-shot win, but it does give you a great fighting chance and - once you get the combo - you'll also get an amazingly hilarious win condition!