Hearthpwn

After trying and failing to beat Free Medivh with C'Thun Priest upwards of 20 times, I tried to come up with a better solution. The goal of this deck is pretty straightforward. Stall the first phase using lots of taunt minions and ramp your jade golems up as high as possible. Use healing touch and armor gain to stay alive in the first phase. (Note: Fandral is helpful but not necessary if you don't have him)

Mulligan/First Phase:

Mulligan for Innervate, Jade Blossom, and Tar Creeper in your starting hand. Turn 1: Innervate->Jade Blossom. The AI will probably trade with the 1-1. Turn 2: Tar Creeper. Turn 3 and beyond: hope you draw all your taunts on curve. You can actually afford to hero power/pass on one or two turns with all of the healing in this deck, so don't be discouraged if you don't have a play every single turn. Once you have board advantage drop Auctioneer and start ramping up your jades with Jade Idol. You will need very big jades to end the second phase; the necessary size depends on how many you can summon, but keep in mind you will probably have to get through a taunt and Malchezaar may Siphon Soul one of your jades. I was able to win with my jades at 21/21 and I summoned four of them. Just before killing Nazra use Earthen Scales to gain a ton of armor. You will probably be at low health and Malchezaar can deal a lot of burst damage (a minimum of 16 damage before you kill him).

Second Phase:

Once Nazra is dead Malchezaar will wipe your board so be ready to summon more jades. If you don't already have a hand full of 4 or more Jade Idols, save an Auctioneer so you can refill your hand as you summon golems. Summon as many jades as you can after Malchezaar hero powers and go for the win the following turn. I was able to win second try with this deck, but the boss is very RNG based as you need near perfect draws to win. Good luck!