Aoe needs to be completely removed from pally, otherwise they will forever limit the possiblity of other aggressive decks. If all it takes is one minion to live to turn 5 to get clear the opponent board and build a 12 attack minion, class is broken.
Remove all AOE from Paladin, no other nerf will work.