As far as recruiting goes the idea of mercenary units for the basic troops is a good one. This covers also that there are graveyards/battlefields all over the map.
As for special units you could do these as buildings in a loose sense of association. Instead of building them it would mean that the burial mounds / graveyards where these units are normally recruited (re-animated would be a better word) are discovered by the faction.
Probably a good building for choice would be the church as it is razed if a region is conquered by a different faction.