I dicked around with this when I was thinking about separating Gief myself. The problems are his scars and hair on his legs, making most palettes look like crap when he's wearing "pants." The best I could come up with was something like this:
As you can see, the scars and hair have to be separated on each leg, since in most sprites they are a shade off from each other. Even so, doing this isn't perfect as seen here:
Some sprites you can still see the outline of the scars/hair, and it would probably look worse in motion. You can get some (kinda?) cool stripes/flames on his pants with this method though. Not much else you can do without manually editing his sprites, which is never cool.
