Hearthpwn

Disclaimer: All cards, with the exception of Alarm-o-Bot, are replaceable. If you do need to replace any of them, I recommend big, beefy, taunt minions. I'm keeping this with Classic cards only, to keep it Standard, but don't be dissuaded by the dust price – swap if you have to! You should also know that this strategy works across many other heroes, with the exception of Hunter, Mage and Paladin, all three of which utilize different, cheap, murloc decks.

Mulligan hard for Alarm-o-Bot and Shieldbearer, but I highly recommend replacing the Shieldbearer with Stubborn Gastropod. Sometimes you only need the Bot, depending on what the Lich King plays during his turn two. If he plays the 3/4 minion and you don't have a taunt, you'll need to restart.

Strategy from there is to simply load up the board using the Bot. Early taunt minions are helpful to keep it alive. Be sure to take your time getting a full board during his immune phase, so you're not scrambling for lethal afterwards.

Credit to the following Warrior deck for its inspiration. This one works across so many other heroes too:

http://www.hearthpwn.com/decks/923843-easy-and-cheap-warrior-vs-the-lich-king