Hmmm.. what if you scaled EVERYTHING up? I would have to see the rest of the game design, maybe this wouldn't work. Looking at the little guy, I think 20x20 is a decent size for him. What if you kept it at that size, and animated him at the size he is now? He would keep his blocky pixel art feel, but the actual animation could be a little more fine tuned and detailed than the extreme limitation you've put on him.
Think about it.
It might not break the stylistic aesthetic you decided upon when making tiny pixel art.