Retributionpaladins. The strength and stamina bonuses are decent, and the crit rating makes it all the more incredible. At level 60 (just as you are getting the hang of Outland), this weapon is relatively easy to obtain.
FeralDruids. Although druids benefit more from Agility then Strength, (Agility gives 1 AP and crit per point, while Strength gives just 1 AP per point), the high stamina, and critical strike rating make this a decent weapon for a druid starting in Outland.
After killing Vazruden and his dragon Nazan, a chest will appear in the back of the rampart which should contain the Hellreaver polearm (Roughly a 16% chance the chest will contain it).