Well here we are again, it's always such a pleasure!
Once again the priest deck will save the day from an angry, angry Naxxramas boss.
Keep in your hand Divine Spirit/Inner Fire and steal his 20/2 weapon using Mind Vision and Thoughtsteal. That's all, really. Then punch him in the guts just like Superman did to the chicken androids!
Bloodsails will be better than oozes in this fight, his weapon will always have only 1 durability in your turn and since he will always play it turn 3 you will be able to do Bloodsails + Thoughtsteal without wasting a turn.
As always, have fun!