Well with the different animations you could just keep the same sprite object and 'play' the different skins? Having each character separated isn't a bad thing either but to minimize it I guess you would do it with animations so the character object is the same but they 'look different'. If you're changing all characters to blue when blue is chosen (just trying to picture the game) I guess you could set each blue animation to be called 'blueskin' and then make all characters set the 'blueskin' animation when blue is selected.
When you say making animations is kind of odd, what do you mean? Surely the animations need to exist already to display the skin?