Hearthpwn

Hey there! This is the deck I used when I was collecting data on Zinaar's Heroic deck - I managed to burn through his deck first try with little problems, so you should have no trouble beating him with this!

Mulligan

You're looking for good early control - a lot of his earlier minions have very little health, so Arcane Missiles, Frostbolt and Annoy-o-Tron are easily enough to take care of them. Mad Scientist is also a good early drop, but since we preferably want to play spells with Flamewaker, I only ran one.

Secrets

Secrets are your friends! Ice Barrier is great armour against any attacks that manage to slip through the cracks, and Ice Block is a good safety net - I only have one, and it didn't proc, so I don't think you'd need to run two.

Strategy

Trade, Trade, Trade. Only go face when he has no minions on the board. Classic combos include the ever reliable Doomsayer and Frost Nova, and Flamewaker and Zinaar's lovely Wishes which he gifts you.

Make sure to kill his Anubisath Sentinels last if at all possible (he has two of them), and don't be afraid to 'waste' an Arcane Explosion on one minion - if it clears the board, it's a great move!

Most importantly, when you're discovering cards, don't go for what looks flashy - you're looking for control tools and healing. Pick the Antique Healbot over the Sneed's Old Shredder, the Cone of Cold over the Arcane Blast, and so on. I'd also suggest favouring Secrets over other cards, as Zinaar tends not to play around them well.

Alternative Cards

Clockwork Gnome: A very good combo with both Goblin Blastmage and Flamewaker as DanHakimi pointed out, this is a good aggressive alternative to Doomsayer that helps you clear the board using the aforementioned cards. It also gives you a Turn 1 play, which is always nice.

Ironbeak Owl: A great way to help deal with his Anubisath Sentinels, Stormwind Champions, Mounted Raptors, Pit Snakes, Fireguard Destroyers and Dunemaul Shamans (all of which he has two of). If you're lacking a Doomsayer and Ice Block this is your best option for a cheaper deck. Try and keep at least one Doomsayer though, it's a very good combo.

Saboteur: A great card against an auto-cast Hero Power. A good alternative to a Doomsayer and Ice Block for a cheaper deck, or if you want to keep them in other cards to replace would be Arcane Explosion and one of the Ice Barriers. Make sure to play it when he has the mana to play the Hero Power though - any earlier and you lose out on a Wish card!

Big Game Hunter: Not always useful, but can be used to remove any larger minions buffed by Stormwind Champion or Anubisath Sentinel. A good fit in the 3 slot if you're missing Ice Block.
_________________________________

Have fun with this! It's probably the easiest win I've ever had in a Heroic mode, but I could have gotten lucky, so if you have any improvements or suggestions, make sure to leave them below and I'll add them to the list.