Update #2!! USE THIS DECK INSTEAD: http://www.hearthpwn.com/decks/621393-heroic-cheap-chieftan-scarvash
Quick update: with Molten Giant nerf, this deck is pretty much obsolete. I'm trying to find another solution.
He starts with 2 on board, starts dealing damage immediately. You can play Doomsayer round 2 to clear or drop Annoy-o-Tron to stave off some damage (Zombie Chow good too). It's good to note that you shouldn't worry if Doomsayer or Annoy-O-Tron get killed immediately. They are just there to harass while you draw more cards. They are not the game winning cards.
If he drops a secret, do not use your hero power.
Utilize minion heals and wreck him with giants.
Substitutions: Sylvanas Windrunner is a GREAT substitution.
Edits: I've replaced Sea Giant x2 for Sludge Belcher x2. I also swapped out the MC Techs for KT and one Corruption for round 1. I've been reading a lot of what you guys have posted and I think these changes will push the deck in a better direction. If you have KT and Annoy-O-Tron in hand, try to hang on for the combo. With both on the board, the AI will not attack at all.