Hearthpwn

The Lich King is easy right up until turn 7 when he always plays Frostmourne which summons six 2/6's. He can continue using Frostmourne without loss of durability until all these minions are defeated, so this deck revolves around clearing them efficiently. 

Use pirates to get early board control.

Save Cyclopian Horror until turn seven when he summons his 6 minions, from now on lets call them bitches (a little salty). If you can get Brann Bronzebeard out on turn 5 or 6, Cyclopian Horror can get up to 3/15, which provides a lot of stall time. 

Use Mind Control Tech to steal one or two of his bitches, depending if you have Brann Bronzebeard out. Then use Crazed Alchemist or Kooky Chemist to flip one or two 2/6's into 6/2's and trade efficiently with any pirates onboard (or cannon shots). If you can get a Cult Master out early you can get card draw from trading out the pirates.

As an experiment I threw Harrison Jones into the deck to verify that it will not work, but was pleasantly surprised when I drew 6 cards (with Brann out).

Worgen Greaser is in the deck to help clear any remaining bitches since they double trade efficiency as well as provide some late game damage to finish the Lich King off.

Good Luck.