Hearthpwn

So, I want to start by saying that this deck does NOT provide the best chances of defeating heroic Highlord Omokk. You will likley need a few tries to get him, but eventually the game should go you're way. No, I designed (and posted) this deck to support new players. As a new player myself, I was blown away at how many decks on these websites require Naxx and GvG cards, which are now classified as wild and of which the adventures are no longer available. I understand that such cards can be crafted, but such actions would be a waste of dust, especially for new players. No, the deck that I have posted here is made up entirely of standard cards that are easily obtainable to new players. Note that this deck does require a couple of cards from BRM (which you have obviously already purchased if you're attempting heroic omokk) and a few from League of Explorers.

Second, I cannot take credit for this deck. Although different in a number of ways, this deck was put together based on the design/strategy outlined by Modnar935:
http://www.hearthpwn.com/decks/233739-mage-fatigue-for-heroic-highlord-omokk
Based on his strategy, the following counters are in place in this deck:

• 2x Abusive Sergeant, 2x Elven Archer, 2x Loot Hoarder are still countered by: Fireblast
• 2x Cruel Taskmaster are still countered by: Bluegill Warrior
• 3x Ogre Brute, 2x Ogre Magi, and 2x Dunemaul Shaman - countered by: Wolfrider + Fireblast, Forgotten Torch + Fireblast, Argent Commander, or Dragon's Breath (naturally, Flamecannon is a more efficient removal than Dragon's Breath, but if don't have this card...)
• 1x Mogor the Ogre, 2x Boulderfist Ogre, and 2x Ogre Ninja - countered by: Fireball (although an additional Fireblast may also be needed), Wobbling Runts (see 'Modifications' section below), and Roaring Torch (as from Forgotten Torch). These minions are also likely to be the target of your Polymorph and/or draw out your AoE spells. If you're lacking the necessary removal when Omokk plays these cards, you may also consider stalling a turn by playing a Mirror Image (see 'Modifications' below).

Note that the real fight in this match-up comes down to how well you control his big minions (i.e., mogor, boulderfist ogre, and ogre ninja). In particular, I would attempt to save your Vaporize counter for when Omokk plays his Ogre Ninja. Either Omokk will go face with the ninja on his next turn and the counter will remove it, or Omokk may play another minion with his charge combination (in which case a removal of this minion is likely just as good).

Modifications:

• 2x Wobbling Runts are added as additional counters to any of Omokk's high valued ogres: Ogre Ninja, Mogor the Ogre, and/or Boulderfist Ogre. Specifically, Omokk's hero power will destroy your 2/6, leaving you 3 2/2's. In my match-ups, Omokk tended to use a board-control strategy over going face, so in these situations, he would attack one of the three 2/2's, leaving you the other two 2/2's to finish off the minion on your next turn (with an additional fireblast needed to deal with a boulderfist ogre). However, I'd recommend keeping the runts to deal with Omokk's ninjas if you have a choice, but don't keep the card if it means leaving one of Omokk's big minions on the board.
• 2x Mirror Image are added as an additional counter to Omokk's Ogre Ninja. Without a Vaporize or Wobbling Runts in hand, you have little/no ability to handle these stealthed minions. Indeed, what tends to happen is that you essentially 'lose a turn' as any card you play can only do face-damage to Omokk (which is a waste in a fatigue strategy). Furthermore, this allows Omokk to add a second/third minion to his side of the board and/or buff his 6/6 ninja (that goes face to you) during his next turn. Naturally, this can get real dangerous really quick in this match. Instead, I added mirror images to this deck to both prevent face damage and 'force' his ninja out of stealth (Omokk's hero power removes one taunt, but requires his ninja to remove the second). This leaves you the next turn to remove the ninja (now unstealthed) and possibly any additional minions he may have added (this may be a good time to use some AoE and/or your Polymorph). Note that this strategy only works if Omokk has the one (big) minion on the board. If his side of the board has numbers, your only chance is to stall/remove with AoE (otherwise, you may want to concede and try again).
• 1x Iceblock are added as an additional layer of protection. Without Antique Healbot from GvG (as used in Modnar935's deck), there is likely going to come some point in this match where Omokk has lethal. Indeed, there is little/nothing you can do to control the burst damage from a Dunemaul Shaman + Charge + Abusive Sergeant combination (this does happen from time-to-time and will make you want to pull your hair out), from his Ogre Warmaul, or TIME FOR SMASH (the best is when he plays 2-3 in a row on an empty board and/or when buffed by a Ogre Magi). As such, having a fail-safe in place (you may want to consider having two in your deck) may save the match for you.
• 2x Forgotten Torch is a really valuable card in this fight as it provides a source of removal for Ogre Brute, Ogre Magi, and Dunemaul Shaman (when used in combination with fireblast). Additionally, this card shuffles a Roaring Torch into your deck which can remove Omokk's Ogre Ninja, Mogor the Ogre, and/or Boulderfist Ogre.

Additional Consideration:
Counterspell - I experimented with this card and received mixed results. It is not a bad card in that it essentially removes one of Omokk's spells (TIME FOR SMASH or Flameheart), but the other secrets tend to be more valuable in this match-up. If you're lacking any of the above secrets, however, it is not a bad card to carry. Indeed, the first time I beat Omokk, I had not yet unlocked the vaporize cards and so I ran with 2x Counterspell instead, which did well preventing damage from TIME FOR SMASH (which gets dangerous when buffed by Ogre Magi). Given that the strategy in this deck is one of fatigue, note that counterspell'ing his Flameheart cards is not exactly ideal...