Hearthpwn

This deck builds on the freeze mage archetype to neutralize Omokk.  A similar strategy worked on Sapphiron in Naxxramas.

Omokk's deck is mostly ogre cards.  The Boulderfist is 6/7 and the Ogre Ninja is 6/6, but most of his other minions have 4 or less, which means it's really easy to set up a massive board clear by stalling with your freeze effects and then using a Flamestrike.

He has a spell that does 5 damage and gives him 5 armor, and a spell that gives him armor and draws some cards.  Counterspell will help with those. 

Omokk will destroy one of your minions each turn.  Since it's random, stealth and abilities like the Faerie Dragon's won't protect them.  So, the only creatures we run are Boom, who protects himself, sort of, with his boombots, Antonidas, Alex and Sylvanas.  

We're also running duplicate to get an extra go at a Boom, an Antonidas or a Sylvanas.

If you can, summon Antonidas the turn after Dr. Boom, that's great, because it might help Antonidas live a turn.  Then, you can fill your hand with fireballs and kill Omokk very easily.