Hearthpwn

Won with this in my first try, it's pretty OP, you'll basically take advantege of her's hero power to "spam" minions on the board, using cards like the Muster and the Tidehunter.

Aldor Peacekeeper is here so you can make favorable trades, saving your minions and dealing with her's.

There are also a few cards that have bad bodies but insane battlecries, like Antique Healbot, cards like that are really op in this mode. I don't use the Bomb Lobber, but I would highly recommend using it.

Some cards are here just to deal reach damage and healing/drawing, I used those because I felt like doing so, but feel free to switch them for other cards as you wish, it's a pretty versatile deck.

Also, this deck is really fun to play against her in Normal and even Heroic mode, so this will also be usable in the Lady Nas'jar themed Tavern Brawl(that is probably coming).

Have fun!