This is the deck I used to defeat Lady Naz'jar on heroic. Her hero power on heroic doesn't replace your minions with ones that cost more, so she'll essentially be gaining more powerful minions than you. So this deck's strategy is flooding the board with minions specifically ones that spawn additional minions, then finish her off with Savage Roar.
The first thing to realize is you can't count on the minions in your deck sticking around because her hero power keeps them changing. So the only important thing is to have lots of bodies on the board for Savage Roar.
Battle cries you can count on, so many of the cards have ones that spawn more bodies.
If this helps in your adventures, please leave a thumbs up. Good luck!