Hearthpwn

This deck is a more current version of the original Free Medivh Shaman deck, which you can find here: https://www.hearthpwn.com/decks/625721-heroic-prince-malchezaar-free-medivh

The basic idea of this deck remains: Trigger the transition from Nazra to Malchezaar when you have a Kel'Thuzad buffed with Ancestral Spirit on the board. Remember that at the very start of phase 2 a complete board wipe happens. Thanks to Ancestral Spirit your Kel'Thuzad will return immediately and be resurrected as well, so you have 2 Kel'Thuzads on your side. Being able to ressurrect all dead minions multiple times every turn will get you through Malchezaar relatively easy, especially due to the AI being very reluctant to attack when you have some taunts and Kel'Thuzad on the board.  Phase 2 is easy with this setup, but getting there is the problem.

During phase 1 Nazra will put a lot of pressure on you with her hero power, other charge minions and weapons. You will struggle to get even close to phase 2, let alone have all the tools you need for the transition. Be prepared to try a lot of times.

To get you through phase 1 this deck contains a lot of taunt minions that can take 2 or 3 hits from Nazra's minions before they break through like Psych-o-Tron, Sludge Belcher or Sunwalker. You will take a lot of damage until you can play those, so several healing spells are also included. This variant of the deck also contains some board clear spells like like Lightning Storm and Volcano to help you remove a bunch of minions with one strike.

Mulligan for Hot Spring Guardian, Lightning Storm, Avalanche or Healing Rain to get you through the first turns. Acidic Swamp Ooze can also help, but you should try to keep it for her big weapons like Arcanite Reaper. Don't forget to use your hero power as Stoneclaw Totem can take one hit off you and Healing Totem will also be targetted by the AI when on the board, so it can act as a pseudo taunt.

Try to survive while waiting for Ancestral Spirit and Kel'Tuzad. Nazra will try to destroy your Kel'Thuzad as soon as you play it, so be sure that you can trigger phase 2 immediately or wait until you have the second Ancestral Spirit in your hand to re-apply it before triggering the transition. If you get a clean transition the rest of the game will most likely be a walk in the park.

Good luck.