Hearthpwn

I used this deck to beat it. It took me just a few tries. (Less than five)

The whole idea is to get your C'Thun to at least 72/72 and be in your hand as you kill Nazra. Once you have this it's an instant win since Prince Malchezaar has 60 health and summons 2 6/6 infernals. That totals 72 health and a win :D

The hardest part with this deck is surviving the early game and getting your board set up for the endless stall to buff your C'Thun.

You definitely want to start off with some SW:Pain/Dark Cultist/PW:Shield. Dark Cultist is key here, it has just enough health so the 3/3's won't kill it and go face instead. FYI, Dark Cultist can easily be replaced with Kabal Talonpriest.

Try to get value with the Auchenai/Circle board clear, but be sure to kill it next turn since using your heal every turn is important.

The setup I had that won the game was this: 1x Dark Cultist, 2x Lightwell, 2x Hooded Acolyte, 1x Twilight Elder. From there it was just a matter of killing Nazra's board with Holy Nova/Holy Fire or attacking the 3/4 Dark Cultist into the 3/3 and healing.

The AI plays predictably. Never use the 3/6 Hooded Acolyte to trade unless you can get it back to full health. Otherwise Nazra will attack it. The AI loves killing your 1/3 Northshire Cleric, sometimes you can use it as a sacrifice for a more important minion.

Other tips:

• Never put Nazra below 13 health. She will mortal strike your Hooded Acolytes.
• Never underestimate the damage she can do. With an Arcanite reaper equipped, she can do 12 or more damage the next turn.
• If you have Holy Nova late game save it for a combo with the drake to board clear.
• Try to heal a minion multiple times a turn, even if its not efficient. The goal is to get your C'Thun to 72/72. Every heal counts.