i don't think ur gonna get camo at this scale.
without changing too much i gave him a work-over treating him as i would a game sprite (becoz im addicted).
i think some ppl don't like this kind of outlining and there are ways around it but as far as i know its the most reliable way to make a sprite pop against a variety of backgrounds (in combination with contrast, saturation etc) and when overlapping other sprites.
out of interest i dropped him against a random metal slug screenshot.
i then realised ur grey background wasn't 50% brightness so the value balance was a bit off.
after some tweaking here's a more extreme palette suited more to arcade games perhaps.
here's a comparison fyi...
more tweaking could be done to make it pop more but it should give an idea.
not sure if any of this applies to ur intended use for the character but maybe you'll get something out of it.