How can I beat Grand Widow Faerlina on heroic?

I was eventually able to beat Faerlina with a priest deck that spammed Silence. Against Faerlina, your strategy needs to be two-fold:

1. Play cards to mitigate the effectiveness of Rain of Fire
2. Maintain control of the board

Number 1 is not quite as simple as it might seem -- if you have too many cards in your hand, minions you play will simply be perforated by Rain of Fire before they can do much of anything. Against this, you really need tough, HP heavy minions, since the damage soak they provide is essential to surviving to the midgame.

Shieldbearer's 0/4 taunt is surprisingly effective at this, as is (since I was playing priest) cards like Power Word: Shield. Lightwell helps too, both with its bulk and its heal (and Faerlina will often ignore it)

The second part is a little bit harder. The minion you need to watch out for are the fanatics that increase Faerlina's attack directly. Since they give Faerlina 3 attack immediately, its as if they come into play with a 3/-- charge minion. And the Grand Widow has at least three of them. Again, as Priest, this is where I prioritized my silences. A 2/4 is easy to handle behind a strong taunt minion, but the effective 5/4 when they're powering up the Grand Widow is no joke. Consider also silencing the nerubian eggs, as even if you ignore it, Faerlina is willing to throw inner rages at it to pop it herself.

Beyond that, strong taunts, like Sen'jin and Sunwalker are the way to go. If you can keep her board clear while keeping your hand size down, you'll be in a very good position to survive her onslaught and beat her. Good luck!