What do you think of my approach. Is this achievable at all? is it oversimplified? As I said in the beginning, I want to keep it as simple as possible, but I do not want to endanger my Arduino board in any way, so hardware protection against too big currents is a must have in all possible ways.
My advice is:
Start with a smaller cube, say 5x5x5. You will learn a lot about both the electronics and the software that will put you into a much better chance at being successful when you scale up to 8x8x8 cube.
Your desire to not use shift registers is a poor choice and makes your project require more components and complexity then it needs to. There are special 16 bit serial shift registers that also include programmable constant current outputs that solve the led current control problem. Datasheet: ( http://www.onsemi.com/pub_link/Collateral/CAT4016-D.PDF ) I can't emphasize how much simpler the whole project becomes when using these special shift register/driver chips then if you instead try some other method of current control for the leds. You will need an external source of +5vdc to power the cube, but it will only need to be rated at about 2 amps max output current capacity (64x.02A = 1.28 amps)
Be sure to buy 'diffused' leds as their wider dispersial of light gives a much better effect then narrow beam brighter leds.
Here is a very good led cube project page where you can learn a whole lot before committing to buying stuff. While it's based on using a PIC micro chip the hardware design is 100% applicable to an arduino based project. I used their basic design for my arduino (actually a standalone 328p chip ) driven 5x5x5 blue led cube and while challenging from both a construction point of view and software design (I wrote the sketch from stratch) it was successful from the git go.
Once completed I think you will find the biggest challenge is coming up with creative and complex pattern displays. I found this very tedious and time consuming and stopped after building maybe 6 or 7 pattern scripts. What is really required is some kind of PC based GUI led pattern generator editor where you can build your pattern frame by frame and then get the raw binary data patterns that you can copy and paste into your cube sketch.
Lefty