A friend of mine has had luck with a Freeze-heavy mage.
Between cones of cold, water elemental, and frost nova, you should be able to protect yourself while establishing board presence. Don't forget to add two Flamestrikes to your deck -- they'll wipe all of Anub's 4/4 Nerubians at once, which is great for in the late game when he's managed to keep 2 or 3 on the board.
Your goal is to survive long enough to drop big minions and waste him. Alexstrasza (if you have her) will deal a quick up-to 30 damage for you, while big minions like Boulderfist Ogres can take hits from the 4/4 Nerubians, and wail on Anub if left unattended. I was able to field Gruul as well.
Beyond that, keep some beefy taunt minions with at least 5 health (Sen'jin and Sunwalker are good choices) to soak up and outpace his minion growth.
Finally, Anub will only use his hero power if he can't play cards -- with a little luck, you will have fewer 4/4s to deal with, and eventually be able to push through.