Here are two other possibilities for resolving the bit rate problem:
-
Use some form of data compression, e.g. just send the differences between the current frame and the previous frame.
-
Use a Teensy instead of an Arduino. The Teensy has a direct USB interface which is in theory capable of higher bit rates than the serial port of the Arduino. [Disclaimer: I have never used a Teensy.]
However, you still need to design a way of driving the LEDs that can cope with the large amount of data concerned. The easiest solution technically would be to use PWM LED driver chips such as the TLC5940, although this would be rather expensive (less so if you can use the SMT version). By clocking 8 chains of 8 of them in parallel and using direct port access, you might be able to get sufficient throughput.
Also bear in mind that 1000 bytes of frame data will take almost half the RAM on a atmega328p. You won't have enough RAM to display the current frame while receiving the next. So you'll either need to use an Arduino Mega, or reduce the cube size e.g. to 8x8x8, or reduce the resolution to 4 bits per LED as rob suggests.