Hearthpwn

This is what I used to beat Heroic Sentinel. You should be able to outlast him if everything goes well.

NOTE: This deck isn't optimal for Normal Steel Sentinel. There are much better alternatives for that encounter.

If you haven't bought Naxxramas, Kel'Thuzad isn't really that necessary (but it will make the match easier for you). Maexxna however can be really helpful. Echoing Ooze is just for early presence, you can try to replace it with Murloc Tidehunter.

Play Acidic Swamp Ooze only if sentinel has a weapon and Cabal Shadow Priest only when you can steal a minion. Remember to use your Hero Power too.

Use your removal spells wisely and you'll be fine.