The best way to do this is with a shader and greyscale images. The problem then is to identify the colorized parts and tint them.
You could do this in one of many ways - for instance, if your images don't really have any grayscale components, you could identify how grey a color is and tint appropriately, skipping when there is color.
If you don't need alpha blend (i.e. your sprites could work with cutout shaders), you can then use the alpha channel to store this information - i.e. tint when alpha > 0.
You could also tint when alpha = 255, and scale down to 0 by alpha = 254, so you don't really lose anything else, except your sprites will never truly be solid, but that shouldn't REALLY matter. This could work really well.
Hope one of those helps