Hearthpwn

Deck I used to beat the Lich King as Paladin, using cards from my limited collection.

It is based on this deck: http://www.hearthpwn.com/decks/918565-f2p-lich-king-paladin

However I'm missing quite a few cards from it (namely the secrets, Abusive Sergeants, Blessing of Wisdoms, my luck in opening classic packs), so I had to make do with what I have.

The key cards here are: Young Dragonhawk, your main minion

Buffing cards: Blessing of Might, Blessing of Kings, Dark Conviction, Adaptation, Acherus Veteran, Master Swordsmith (proved to be useful in my successful run)

Anything that gives divine shield: Hand of Protection, Argent Protector

And Truesilver Champion for removal/face damage

I then filled in the rest with low cost taunts and card draw. Perhaps the taunts can backfire on you, but stuff like Goldshire Footman doesn't have the best of stats, so you can kill it easily with your other small minions.