Still no go. One sprite is 8x8, 3 colors + alpha (one color is always alpha? Can't have a tile with 4 colors without alpha? have to check on that)
I can't slice bruteman to 8x8 pieces without some pieces having too many colors.
8 sprites per scanline and at the tip of the axe there's a part that needs at least 7 sprites. So width is the issue here.
Notice how stone man is exactly 4 tiles wide and 5 tiles high. The face has two sprites on top of each other. Same with the red sphere.
So at maximum stoneman has 5 sprites on one scanline. Megaman has 3, so that's a total of 8, so stoneman probably flickers when you shoot at him.
I'll check around for NES sprite editors to see how the enemies are built.
-Edit-
Here's how stoneman is divided. His legs are mirrored and use the same tile.

also portrait

16 tiles + 3 sprites make the final image.
(NOTE that the black is actually transparent in the portrait and shows the BG fill color, so there's no black in the tiles or sprites.)
Technical things aside, i really like bruteman. He fits megaman and has character. With a bit of headscratching it should be possible to get a result very similar to what he looks like now AND meet the restraints too.