This could be done using colour-keying.
This would work much in the same way that green-screening works for TV - look for a particular colour and replace it. It's quite common for this to be a colour not normally used (and quite garish) like magenta.
Some SDKs (like SDL) have direct support for this, but you can easily add it to any shader that draws a sprite, just like you'd expect - look for your colour and replace it with one specified in code.
Of course, if you're dealing with more complex situations (like multiple customisations) you need multiple different colour keys. At this point, the simpler solution might be to use transparent sprites, a range for each part, and then composite them together afterwards by drawing one on top of the other.
I'm going to use your example above about a character with a head, body and legs since it's a bit easier to understand. :)
Since you can both change the shape of the item (different shape heads, male/female heads) and also the hair colour (red, brown, blonde, blue...) you could have each head shape and then have the hair pixels marked in your colour key, for example all hair is magenta. Then, you can overwrite magenta with red, brown, blonde or blue.
The downside of this is that it needs to be an exact colour match, so you couldn't do shaded colour from this approach. However, if you separate the image out into a mask and the detail, you can colour-key the mask and then add semi-transparent detail on top.
This would work based on alpha blending - much in the same way that if you overlay one colour at half opacity over another, you still get some of the previous colour. This then requires that when you're developing your assets, rather than picking the colour you want you need to have a layer underneath of the 'base' colour that's going to be replaced by magenta and then you have to put a colour on top that creates the desired difference you want. In this case also, you detail will more than likely be in black and white or it won't apply nicely across all the colours. Sadly my pixel-fu isn't strong so I can't really show you an example.
In short though, it's an awful lot of work just to save a bit of memory in assets - you could probably be better served by breaking things down into smaller parts (in this case, separating the hair from the head) and then making each iteration of them.