Earlier quoted context omitted.
For this to work, you'd want two adjacent faces painted, rather than opposite faces being painted, which seems to be how they're currently done (unless they only have one face painted?). Then the four possible rotations would allow for each possible pixel-pair. (The cubes could perhaps instead be squat rectangular prisms, to correct the aspect ratio, too.)
Likewise, if you generalize to 3-face array, you'd need an octagonal unit painted in a 2^3 debruijn sequence...
... But that's as far as you could take it, since 16-gons would show at least 7 faces while only having an encoding for 4.
I also thought of using hexagonal prisms, showing two faces at a time in paired colours but using three colours. These would also need much less clearance in order to rotate freely, compared to face-on cubes.