UPDATE: I decided to test this a bit again and it hasn't been working out as it did when I first made it. I made a Shaman version (the same idea as this) and so far it's been working far better than the Hunter. You might want to try it instead: http://www.hearthpwn.com/decks/457981-heroic-anubrekhan
After all the decks I found to beat Anub'Rekhan in heroic failed to work, I decided to try to come up with something myself.
The result is this deck that I won with on the 3rd try.
This deck wins by abusing the AI bug, where the computer will not attack if you control Kel'Thuzad and a Taunt minion (because really, how the hell can you beat him pumping out a 4/4 every turn).
Mulligan hard for Bear Trap, Hunter's Mark+Arcane Shot, Deadly Shot, and Tracking. The premise is that the only minion in your deck is Kel'Thuzad. When Anub'Rekhan plays Deathlord, you kill it (usually with Hunter's Mark) and get KT on the field, then follow it up with Bear Trap. After the next time Anub attacks you, you get a taunt and he will never attack you again the rest of the fight (it's also possible to use Misha from Animal Companion, although this is a less reliable way to get a taunt). If at any point you draw Kel'Thuzad (or find him in a Tracking), concede immediately as there is no way you can win.
Note: not every spell in the list is required. I used some of them simply as filler because the only minion can be KT. The flex slots in this list are Explosive Shot, Multi-Shot, and Ball of Spiders. Feel free to replace these with other spells/weapons (Personally, I like Ball of Spiders as it might get you either Ironfur Grizzly or Silverback Patriarch which can both serve to replace the Bear Trap).
Things to look out for:
- Locust Swarm: Never let Kel'Thuzad get down to 3 health or this might happen, losing you the game instantly.
Good luck! Don't forget to upvote if it works for you!