Hearthpwn

Heroic Sapphiron still uses the Frost Breath hero power to kill all your non-frozen minions every turn, but this time, you get no Frozen Champion to hide behind.

A deck built around freezing your own minions isn't very efficient, so a mage deck with very few creatures is the obvious choice for this boss.  The trick is that Alexstrasza is banned on the fight, so the usual freeze-mage finisher isn't going to work.  You're going to have to use your spells to beat down 45 health, which is tough, especially while also managing the board.

Amaz apparently beat Sapphiron with a similar deck; I am in North America, and we are the last to get the wings unlocked.  This deck has a few differences, though:

First, I included a couple of counterspells.  Sapphiron has a spell that deals 9 damage to the face for 5 mana, and his deck has few enough spells that you are likely to catch it with your counter (he also runs frostbolts).

Second, I included some Ice Lances and Archmage Antonidas.  The damage you can do with spells is pretty tight, so without him, you're kind of dependent on hero powers.  You can Ice Lance Antonidas to keep him alive, if Sapph doesn't have a board that can kill him, or you can just drop him on turn 10 or later, Frostbolt+Ice Lance Sapph in the face, and get two free fireballs.  

I also pulled out the Nerubian Eggs, which are 4 damage each, and put in Bloodmage Thalnos, who can make a Cone of Cold kill some Faerie Dragons, or can beef up your Ice Lance combo or your board clear, and gives you a card when Sapph kills him.  But if you don't have him, the egg is a perfectly fine substitute.