The best way to do this would probably be with ColorReplace() [
see documentation ]. You can use ColorReplace to change one specific colour to another in an image. This means you won't have to maintain a specific pallette, you can just draw all your character pieces in one colour and then replace each of the shades you use on the fly.
This'll probably be pretty slow if you try to do it every frame, so I suggest saving an image of the pallette-swapped item and just blitting that each time the entity is drawn.
Does that make sense?