What I'd like to do is that every unit I build is renamed using a certain model. For example, the 2nd Grenadier that gets built in Paris would be automatically called 'Paris 2nd Fusiliers', the 5th Cavalry unit would be 'Paris 5th Mounted', 16th cannon built in Paris would be 'Paris 16th Bombardiers', and so on.

Is this possible, and how would I go about doing it? I figure that it should be possible, because Sevo'd mod has the Canadian Corps unit, which automatically gets a unique name when you build it.

Yes, very possible. I just did a quick scan of the mod components forum and there are several, but none seem from a brief glance to do this. I know the unit stats mod (http://forums.civfanatics.com/showthread.php?t=162977) has several name generators in, but I'm not sure of the details.

If you want to do it yourself you'd have to have a tinker with some python codes. It probably wouldn't be too hard to adapt a name generator which is already out there.