WARNING: This deck is meant for people who lack a lot of the good cards to make this boss.
Anyone that started the game just now and completed Naxxramas can do this deck!
Start with Acidic Swamp Ooze in hand to counter his weapon. And Unstable Ghoul to avoid direct damage.
You will be given this card during the match sometime, and it will help you destroy his weapon. Destroy his weapon when you have no taunts and his weapon attack is above 5. If you have Grim Patron on board and his weapon attack is 1 try to play around Grim Patron attacking minions and face and avoid playing cards while his weapon is up.
By following third step you will eventually beat him either with grim patron wither with Loatheb.