Hearthpwn

This is the deck I used to beat the Lich King with paladin. The main strategy is that your murlocs are dying twice because of his special power. Try to kill off your murlocs (best combination is warleader and old murk eye leaving the bluegills for later) and draw as much as possible to play doomsayer on seven. It kills all the ghosts and then it ressumons in his side and it clears whatever was on the board before turn seven. Then survive until turn ten and play anyfin. I've heard that many people were struggling with paladin and it didn't seem that hard to me with this decklist so I clearly recommend trying it if you're stuck.