Hearthpwn

          Right off the bat this encounter is horribly designed and unfair, but you probably already figured that one out. Hopefully this deck will help you get the card back for Karazhan.

          The main win condition of this deck has two parts; trying to survive the first stage of the fight by playing lots of taunts and healing, while the second consists of building up bigger Jade Golems to one shot Malchezaar.

Stage one:
          This part is the worst by far because of the aggressive nature of Nazra's deck. Almost every time she will coin out her 3/3 charger on turn one (unless she is holding a Frostwolf Grunt). This is problematic as the damage stacks up quickly so try to stabilize the best you can by playing as many taunts as you can. There are some jade cards in the deck to start building up your Jade Golems earlier (try to give the big ones taunt!) 
*Note if possible play two smaller taunts on a turn as opposed to one big one, this plays around Execute better and hopefully baits one or both out.

Stage two:
          If you are in an OK position on the board try to  build up your jade Golems with the Gadgetzan Auctioneer + Jade Idol combo to one shot Malchezaar in the second phase of this battle. Even if your board is full continue to summon Jades as this will continue to increase their attack! Once you have big enough Golems and have enough idols in hand to summon at least 60 damage worth of Golems (i'd summon a few more because Malchezaar has a few taunts in his deck) you can one shot him.

Possible Card Substitutions:
          This particular deck was made from the cards i have in my collection therefore it might not be THE best one out there for this encounter, that being said this was what i beat the boss with.I don't know all of your collections or how much dust you have laying around so change what you think doesn't work or add cards that you have that aren't listed. 

Malfurion the Pestilent - Druid death knight i don't have this card but it might prove to be useful against her as you can summon two 1/5 taunts and gain 3 armor a turn on top of the 5 you gain from casting it

2nd Gluttonous Ooze- this might help for a bit more weapon removal

Hadronox - This guy MIGHT be useful, i dont know if he will be too slow though

Final Thoughts: 
          This fight has got to be my most despised in all of hearthstone as it takes many tries to win and sucks to do overall I wish you the best of luck in beating this and pray for RNG to be on your side.