Pretty much just mulligan for Gadgetzan Auctioneer and Conceal. If you aren't able to get Gadegtzan Auctioneer, just restart until you do. If you can't get Conceal, don't worry. Just cycle through your entire deck until you have enough damage. This plays out like the old meta miracle rogue. I beat this guy after 3 turns, taking no damage, and clearing his board on heroic.
Please upvote if you like it so people can see an easy and cheap way to clear through Nightbane
1. The number of trial runs performed on this deck was minimal. Therefore, there might be a few cards in Nightbane's deck that could lead to a loss early on. Just keep trying and you'll succeed.
2. The 3-4 win condition claim is only met if the situation is perfect. This means that Auctioneer lives long enough for you to draw your deck and he doesn't play any taunts that you can't sap or heal a large portion of his health (3-4 turns isn't that long so the chances are slim but possible.)