This is the decklist I used to successfully beat the Lich King solo mission on my first attempt (with this deck). It's basically a fine-tuned version of the popular F2p Lich king paladin deck albeit with some key differences.
First of all, due the Lich King's special Paladin-specific spell, which makes all of your dead minions resurrect as the Lich King's minions, I removed all non-Young Dragonhawk minions. The primary goal of this deck is to mulligan aggressively for a Young Dragonhawk to drop on turn one, then proceed to buff the minion with +attack, +divine shield, and +health buffs ad infinitum.
With only one minion (that should not die), you won't even need to think about the Lich King's annoying power. Note that mulliganing for Blessing of Wisdom should also be prioritized, as you'll draw an additional 2 cards per turn, but it's by no means necessary (I didn't draw it on my successful run).
In the place of the old deck's minions, I've put in more buffs—a lot more—including some health buffs that the original deck lacked. If you draw well (i.e., enough divine shield and +health buffs), you should be able keep your dragonhawk on the board easily... as long as the Lich King doesn't draw and play Obliterate. If he does, you may as well restart the game.
Seeing as how the upside of this deck is its ability to win before turn 7, i.e., the Frostmourne turn, restarting often in the case of a rogue obliterate or poor draw shouldn't be too much of a time sink. Since I won on my first try with this refined decklist, I can't quite tell you just how often you'll have to restart, but hopefully you'll have similar results.
Just in case you're really close to winning on turn 7, I've also included a copy of Enter the Coliseum, which will clear the board of spirits as well as your dragonhawk (since it will be your only minion). Due to its windfury, your dragonhawk can smash the last spirit and then resume bashing the Lich King's face on the same turn. Based on my own experience, however, this card isn't mandatory.
Here's my turn-by-turn play through of my single (successful) run with this deck:
- T1- Played Young Dragonhawk - 1/1 on board; LK 30 HP/30 Armor
- T2- Buffed with Divine Strength & Blessing of Might; 5/3 on board; LK 30 HP/20 Armor
- T3- Buffed with Seal of Champions; 8/3 (DS) on board; LK 30 HP/12 Armor
- T4- Buffed with Blessing of Kings; 12/7 (DS) on board; LK 18 HP
- T5- Buffed with Rallying Blade & Potion of Heroism; 13/8 on board; LK 5 HP
- T6- Buffed with Divine Strength & Blessed Champion; 28/10 (DS) on board; LK 0 HP (WIN)
Of course, I got pretty lucky with my draws, and really lucky with no Glacial Shards, a complete lack of obliterates, and few taunts, but I won by turn 6 on my first try!
The only minions I had to deal with were a Val'kyr Shadowguard on turn 3 and one-half of a Saronite Chain Gang on turn 5 (the rallying blade was clutch for the other half). Otherwise, the minions that were on the board didn’t attack my dragonhawk for whatever reason… results may vary.
I hope this deck works as well for y'all as it did for me... Good luck!