I used priest my first play through. The deck was essentially the same as the 'Amaz' deck, but I ran two Sunwalkers instead of Rag and Faceless. You could also run Mass Dispel, Sunfury Protector/Defender of Argus with Ancient Watchers and/or Silence.
I've noticed a lot of other people finding themselves at a point where they have drawn their deck and fatiguing before they win.
Alternatively you could run Freeze Mage or Control Mage, like the deck @Raven_Dreamer mentioned.
I've also beaten Anub'Rekhan with the new Zoo variant that Kolento has introduced.
There is a fair few guides on reddit that go more in depth.
