Let me just start off by saying I'm well aware that being able to change your player color has been suggested before, these are merely my ideas on how this could be implemented into the game.
So here's what I think the best way to add this feature into the game would be like. You know our good friends Punch and Vise, correct? They upgrade our weapons and unbind a weapon we want to trade respectively. Seeing as how Vise seems to have the ability to tinker with our knights to have a weapon no longer be bound to us, having a third gremlin for changing our colors doesn't sound too far fetched.
So this third Gremlin (for my sake I'll just call him 'CC' for Color Changer) could have a layout much like the others, having a ticket for each color. You merely select the color you want from the list and your player color changes, after paying a price of course. Much like Weapons and Recipes, CC's wares could have a preview option so you could see what the new color would look like on whatever you're currently wearing. CC would be in the same general area as the other gremlins for easy access.
As for the price of changing your color, I'm thinking 200 CE would be the right price. That's around the price of any other upgrades you could buy. Seeing as how changing your color has no affect on your abilities and is purely for looks, I don't think the price should be much higher. Those 200 CE would add up if a person came back to change their color more than once.
Personally I'd just be happy with being able to change my color, but there are also other things you can add to make more people want to use CC.
New Colors: So we've already got a pretty large selection of colors to choose from, but there are a few like black and white that we can't choose. These new colors could be specifically just for those that buy the ticket from CC, instead of making it available at the start when first creating a character. Think of them as premium colors.
New eyes: This doesn't have to do with colors, but it's in the group of looks. For female players there could be feminine eyes with angry eyes, happy eyes, anything really. This could also be done by CC, possibly in a different tab section much like Brinks has his items.
And those are pretty much all my ideas for color changing. Frankly I don't care how you guys go about doing this (if you ever do), but I'm hoping my ideas help in some way.
I had the same idea! with the CC gremlin, but i thought he could look like a french painter?