I still say we should go with Mercenaries, and it would only require a few changes -

1. Mercenaries can only be recruited during a civil war, or by an edict
2. At the end of a civil war, all Mercenaries not recruited through edicts (that have not expired) are disbanded
3. A player involved in a civil war may only recruit 1 mercenary per turn, and only up to a total number of their prioritizations per term.
4. The recruitment is based upon first come, first serve.

I know this is very basic, and I wouldn't mind some feedback to see where this can go.