Best Deck to Beat Instructor Razuvious in Heroic Mode
Instructor Razuvious will summon very powerful weapons that will kill you in 2 turns. Therefore you need the Acidic Swamp Ooze and a deck with many taunt minions. The best deck to beat Instructor Razuvious is a modified version of Warlock Handlock shown below. Other decks that might work is Freeze Mage if you focus on freezing Instructor Razuvious and put in some strong taunt minions.
Beating Gothik the Harvester in Heroic Mode: http://wp.me/p1SfP0-1Lt
Beating The Four Horsemen in Heroic Mode: http://wp.me/p1SfP0-1Ls
All Naxxramas Heroic Mode Guides: http://wp.me/P1SfP0-1L4
Best deck to beat Instructor Razuvious:
Class: Warlock.
2x Soulfire
Power Overwhelming
2x Ancient Watcher
2x Acidic Swamp Ooze
2x Sunfury Protector
2x Sen’jin Shieldmasta
Hellfire
2x Defender of Argus
2x Sludge Belcher
Harrison Jones
Leeroy Jenkins
2x Twilight Drake
2x Faceless Manipulator
2x Siphon Soul
2x Sunwalker
2x Mountain Giant
2x Molten Giant
Best Strategy to Beat Instructor Razuvious in Heroic Mode
Play Warlock Handlock as you would normally focusing on having a taunt minion out when Instructor Razuvious has a weapon out. Note that it might take a few tries to beat Instructor Razuvious in Heroic mode and a good starting hand. A good starting hand would be one that has a Mountain Giant or Twilight Drake together with a taunt giver such as Sunfury Protector and Defender of Argus. You will also need the Acidic Swamp Oozes to get rid of Instructor Razuvious’s early weapons.
auluftwaffles.com, short video game guides 
I used a pretty simple paladin deck, he trick was planting an eye for an eye card when i was out of taunt so he dealt 20 damage to himself which really helped in the match
what can i put in instead of leroy jenkins and harrison jones
what if u doint have Leeroy Jenkins
It took me a few tries, but the deck worked fine for me!
For those who are looking for alternatives to Leeroy (btw. I didn’t need him. I was happier with Taunts and Giants.), try the Arcane Golem.
Put two Bloodsail Corsairs in the deck. You need the weapon removal.
Won first try with this deck, up your game Anon.
swapped one Siphon for Corruption and Harrison for Rag
My deck with the differences below beat it easily on non-heroic:
no Ancient watcher so 2x goldshire footman
no Sunfury protector so 2x frostwolf grunt
no harrison jones only 1 sunwalker so 2x unstable ghouls
no leeroy jenkins so Alexstrasza
no Faceless Manipulator so 2x ironbeak owl
only 1 siphon soul so 1 addt’l power overwhelming
no molten giant so 2x shieldbearer
For Heroic Gothik: I’ve found that Iceblock does NOT prevent fatal damage when it occurs from the explosions and/or the spectral ‘ping’s’.
not even close of winning with this shit
As I said in the post it might take a few tries but it shouldn’t be a problem. Even with a good deck the fights are still hard. There are also some priest decks out there that might work for you.
First try with this deck and I smoked him like a salmon. Managed to kill one of his death rattle guys and got a free Molten Giant on the field.