Here's the video showcasing proper usage of the deck in order to defeat the Lich King!
The Lich King uses a 1 mana spell which squelches your hero. Yes, really lmao. The change is rather irrelevant and doesn't require you to make many adjustments to any meta Priest deck to find success. Therefore, Mecha'thun is the choice of deck here.
Go for your card draw coinflips here, and Twilight's Call to further mill through your deck. Hemet is another useful mill activator. Your combo is untouched by Hemet and so he can be used with relative impunity. Just make sure not to use him so early you take significant fatigue damage from an empty deck.