Hi.
I read that you tried Motion JPEG and it's too heavy.
Then, how about enlarging the image 8 times?
In JPEG, images in 8x8 px units are encoded only with DC components. Encoding can be done in pixel by pixel, with only lightweight operations like subtraction, table lookup and bit operations.
As of compression rate:
Setting quantization table to all 0xFF and the DC component will be in the range of -4 to +4 (enough for 4 shades),
then difference in range -8 to +8, and by limiting it to -7 to +7, only 0 to 3 bits are required for encoding each number.
By assigning Huffman codes as 3, 2 and 1 bit ones for the 0, 2, 3 bit number, 1 block (= original 1 pixel) can be represented in 4 or 3 bits.
With 1 bit for AC component (it is “all 0”), compression ratio of 5 bits/pixel will be possible.
I don’t know much about Motion JPEG, but I think this may be a feasible idea.
See the sample image file (made with GIMP). Note that however, the Huffman table is not assigned as described above. (Because it was difficult to create such a file.) It's optimal assignment for this image, not for minimizing worst case size.