Not using standard modding techniques. You could do it using some kind of seperate app which worked as a .dm generator though. Like the unit maker, only for assigning random hero monster IDs to the starting scout tags of various nations. Sounds like it might be more work than it's worth.
It could probably be done with the RanDom program. You'd just need to ask the dev to add in options for changing variables of the capital, like starting troops and commanders. I don't think it would be hard to add.
It modifies maps, e.g. by adding a commander with spesific items/troops into a random province or a province that matches certain requirements, like terrain. It wouldn't be too far-fetched to add a requirement "this province is a capital of nation X" IMHO.