You can store 3 masks in the RGB channels of a sprite and tint these areas independently. This method allows for gradients and semi transparent tinting as well, but this is the most basic implementation so any untinted areas will be black (which works fine for your citizens Namelezz).
<img src="http://i2.photobucket.com/albums/y8/soggyclog/tint_mask.jpg">
I put together a basic shader and sample CAP file (edit:forgot to include the .FX file before, but should be there now)
http://www.filedropper.com/colourtinting2
Right now the shader takes independent RGB values for all three masks so thats 9 numbers. I don't know if there's a more elegant way to have just 3 colour pickers or something.
This shader can also be made much more useful if instead of storing the transparency in the alpha channel you store a 4th mask, and then have a seperate sprite beneath the tinting sprite to provide the monochrome detail and blend with an overlay mode. The down side to that would be that you need two sprites per character. But yeay, for this kind of pixel art stuff that's not really necessary.