After trying and failing several times with other decks I decided to make this deck and won 2nd try with it. This is a tough boss and regardless if you use this deck or another deck you probably need some luck to win. The hope in making this deck is that we're a little more likely to "get lucky".
We mulligan for any kind of early turn removal.
Galakrond, the Unspeakable is meant to be played as removal before quest completion.
The win condition is pretty much to complete quest + stick a big minion with lifesteal. Unlike other decks I've seen, this deck does not need Alexstrasza, since we basically heal up to full every turn after we hit the win condition.
Turn 5 Convincing Infiltrator into turn 6 Grave Rune can potentially carry you until you complete the quest, but obviously that only works if the Convincing Infiltrator survives a turn, which is a big if since Illidan has several ways to kill it from hand even if his board is empty.