I don't think the function Leeroy plays is necessarily bad, or that he's imbalanced in a vacuum, but the leeroy + power overwhelming + faceless combo, or leeroy + shadowstep (x2) combo, or the leeroy + UTH combo are all a bit too strong, I think. All of those are class-specific (unlike previous "too good" cards like novice engineer or argent commander) and can be adjusted without actually changing Leeroy himself, though.
Leeroy should have a spell shield like Faerie Dragon, there are just too many spells like you said that make him go out of control. That way you can play him a that neutral fireball or behind a taunt but not do that near OTK's that are going on right now.