I decided to play devil's advocate here and say that outlines aren't necessarily bad. Especially on a sprite this size. Either you're going to want to use something like 3 colors with high contrast or use outlines. If you don't, you'll end up with a muddled mess. The former option is best reserved for nes sprites though.
Anyways, I used some high contrast high, high saturation colors, and the same general dark outline color. Although, I did outline some areas lighter than others to give it a less 2d look.
Please note that I butchered the perspective on his right arm since the original pose looked prety peculiar and confusing. But now his right arm is raised up a bit more and therefore kind of kills it. I didn't really realize it or else I might've pushed it down a bit. XD