Ok, I'm not nearly as proficient with promotion as ptoing, helm and many others here, but I'd got about it this way (assuming you don't need the two different sprite versions to be in the same frame):
- make sure global palette is not ticked (the capital G at the top right part, right above where you can pick the transparent index# and check/uncheck it)
- ctrl+c to copy the whole frame of the first version
- ctrl+e to insert it again as a new frame (or you can simply click the plus-icon in the animation bar instead of the last two steps)
- change colors as desired in the palette of the new frame without it affecting the first frame
With this
plug-in you can select several colors at a time and then change the hue for them all at once. Though that won't do hue-variation any good.
As for moving colors in your palette, I'd just copy it to where I want it, replace the old slot with black and use Colors->Remap Colors->Frame/Animation (obviously the first option only fixes the active frame while the latter fixes all frames).