I would suggest making the following changes in addition to adding a new soul:
1). Retool rift blade to have solid ranged dps. Change the cooldown on flamespear to instant again. Keep rift storm melee based. Make the damage increase for rift blade to plus 3% melee and plus 3% ranged dps. Redesign rift strike to be ranged dps like a spear on the same cooldown timer. Keep the other abilities melee only. The idea is a ranged dps option that still required melee for max dps. This spec would be used in fights with many disconnects. Also, increase the damage of rift storm. So warriors would get strong ranged dos that would require melee to maximize.
2). Increase paragon single target dps. Keep AOE for the soul at its present dismal level. Due yo the fact paragon is so limited to single target the soul needs a bump in this department. The other option is to increase it's AOE. The bottom line.. It makes no sense for a duel wield single target dps soul to not have the highest single target. Paragon needs a buff.
3). For the new soul add a melee based healer. Heals are correlated to damage done. Like an awesome death knight healing toon.
4). Add more support to warlord. Including abilities that heal the raid. Like bard.
The premise that warriors cannot have a heal soul is short sighted and foolish. Considering the multiple roles that can be fulfilled by other classes. Give warriors a heal soul.