Pixel art is extremely difficult. I'm no good, and I just dialled it in for Escape From Dinosaur Island DX (the loading screen isn't mine), using multipaint (which doesn't have the features you are looking for).
The following website might be a good place to start. It seems to have layers. Not sure if re-colouring is easy or hard (never used this). Others can certainly help you better. I think
If you want to spend money, I hear that aesprite is quite nice. There is a trial version, if you are not sure (can't save from the trial version.