Compiled from comments by Cory Taylor and Steve Herman
For a 2x2 cube or even a 3x3 cube, the combinatorics of the painting requirements are not prohibitive and can be worked out relatively quickly. Beyond a 3x3 cube the color selections get very complex and a more general solution would be required. As the general solution for this is relatively straightforward it will be explained and it can then be applied to any desired size of cube.
For any sized large block, made up of "n" blocks per side, there are n³ blocks total. Each block has 6 faces so the total number of faces available for painting is 6*n³.
Each face of the larger block contains n² smaller block faces, meaning that the block as a whole has 6*n² faces painted. If n colors are used, the total number of required painted faces is 6*n³.
This means that, for any sized block, no face of any block can remain unpainted. At this point we have not shown that the solution is possible or impossible, simply that it needs to be 100% efficient. If a rearrangement algoritm can be derived whereby through several (n) repetitions (of the same algorithm) each face of each smaller block is exposed exactly once, then this algorithm can be used to paint the faces in accordance with the problem requirements.
The following alogorithm (in three steps) successfully rearranges the cubes so that successive paintings after each completion of the algorithm can achieve the desired final result. Moreover, after completion of the painting (painting the "n'th" side), the cube can be cycled through the paintings by repeating the algorithm.
Move the leftmost plane of cubes to the right extreme of the cube.
Then, move the frontmost plane of cubes to the back extreme of the cube.
Then, move the bottommost plane of cubes to the top extreme of the cube.
