Hearthpwn

I started making this as a Face Hunter deck, but added some strong cards as finishers so it turned into more of a fast-paced midrange hunter.

Fast being the keyword, because the less cards you have in your hand for this matchup, the better. Play as many cards as you can so the widow cannot use her hero power effectively against you.

Mulligan: Any of your lower cost minions like Worgen Infiltrator, Mad Scientist, Leper Gnome, Knife Juggler. Don't hold them in your hand; get them onto the battlefield as quickly as possible. 

Strategy:

The more minions on the board you have, and the fewer in your hand, the more her hero power is diminished and less likely to kill your important minions and/or you. 

You could consider putting in a second Unleash the Hounds for this reason. Even if you only get a couple of hounds out of it, they are targets for Faerlina. Haunted Creeper would also be a good card in this deck.

Swamp King Dred is a great finisher and helps keep board control. King Krush is great to have when you need him -- you'll find plenty of uses for him. I like to hold him for a finisher if I can.

Try to kill her as quickly as possible. Ignore her minions for the most part and focus on attacking her face.