Pick an arbitrary (but not really uniformly random) Hamiltonian Cycle over the 4096x4096 pixel grid, and another over the 256x256x256 color cube. Starting at (2048, 2048) and (128, 128, 128), walk along the hamiltonian cycles in-step, placing colors at corresponding pixel locations.
The hamiltonian cycles were generated from a spanning tree of the half-size grids. For the grid, I joined sets of four pixels into separate cycles, and joined them together when they were joined by an edge of the spanning tree. For the pixel cube, I used sets of 8 pixels arranged in a cube.