My first deck submission here. This is the deck I used to defeat The Lich King in the single player mode.
The Lich King's effect on Shaman is turning all minions in your hand and deck into 1/1s.
The deck's goal is to buff Lightwarden with Healing Rain and give it Windfury to swing for 50 damage. Since the Lich King has 60 health total (30 health + 30 armor) you'll need some extra 10 damage, which you can obtain with Flametongue Totem and/or in the early game with minion summoned by Devilsaur Egg, etc. Make sure you take at least 12 damage before you use Healing Rain, in order to maximize the buffs on Lightwarden. That's where Stormforged Axe comes in, to trade with his minions in order for you to take damage.
Steps to beat The Lich King with this deck:
1 - Mulligan for Stormforged Axe and the combo pieces you'll need (Devolve, Lightwarden, Healing Rain, Windfury).
2 - In the early turns try to take enough damage to heal later but at the same time keep some control of the board. Use the draw effects to gather your combo pieces, Stonehill Defender to get some taunts (you will need one later on), Devilsaur Egg can trade and spawn a 5/5 to deal some extra damage to the Lich King early on. Volcano is a last resort if his board gets out of control.
3 - On his turn 7 he will always play Frostmourne, spawning the Souls, at the start of the turn and attack with it, even if he has minions at that time. Therefore, when you reach your turn 7 you need to have the conditions below fulfilled. If not, restart.
- Windfury, Healing Rain and Devolve in your hand.
- Lightwarden on the field. Only play her on your turn 7.
- at least one Taunt minion on the field to protect Lightwarden from the Frostmourne Swing. If necessary use Ancestral Healing or Hex on a Basic Totem or another minion you don't need. You can also use Ancestral Spirit on the Lightwarden if you don't have any taunts.
- be able to heal for 12 with Healing Rain. The best way is having taken 12 damage beforehand.
- have that 10 extra damage already dealt or be able to do so on the next turn. If you want to use Flametongue Totem to buff Lightwarden, put them on the field now.
4 - On your turn 8 use Devolve on the Trapped Souls. This way Frostmourne gets instantly removed and the Lich King loses his immunity. Pray to RNGeesus that the Devolve doesn't give him a Taunt minion. If it does, hope you have Earth Shock in your hand.
5 - Use Healing Rain and then buff Lightwarden with Windfury to swing for 50 damage.
This can take some attempts but eventually you'll get there. Good luck!