After spending fruitless hours trying the highly-ranked Priest and Paladin decks on Hearthpwn.com to beat Heroic Kel'Thuzad and not coming close, I gave this deck a shot and won handily on my 2nd try.
On my first atempt, I made a play mistake and yet still came much closer than I had with the previous heroes. Furthremore, I didn't have to mulligan and concede if I didn't get the right cards, and I didn't need the perfect draw.
This deck burns down KT's armor quickly so you have a decent chunk of life left when he stops freezing you.
In general, the minions aren't that strong and you'll have many of them, so whatever KT steals doesn't have that big of an influence on the board. What makes them strong is their battlecry pump effects and deathrattle summon effects that help the deck effectively trade and race.
I was able to safely Life Tap many times as KT cannot threaten your life total effectively without a board presence.
I hope this helps you. If it does, please upvote it for visibility. I wrote this guide solely because the seemingly best options didn't work for me.
Someone has recommended Shadowflame to clear the 5/5 taunts. I didn't need it at all, but if you're struggling with that part, use it to sacrifice a 5-power minion to wipe his board.