Thank you again for your replies!
Nick Gammon, in a theoretical sense you are right that 16 wires to drive 64 LEDs is pretty good. However, the LED cube is all about being able to see through it, about being elegant, about not seeing wires... I was thinking that I could cheat out half of the wires by dividing the cube not into horizontal, but vertical planes. Each MAX7219 would drive a vertical plane. This way 8 legs (all anodes or all cathodes) would go directly into the PCB beneath the cube, so only an additional 8 wires would have to crawl up along the edges of the plane. Dividing it equally, I could manage with 4+4 wires. Maybe I can buy some very thin wires and it would look nice. I wonder how thin is not too thin. I'm thinking that the resistance of the wires might matter...
CrossRoads, your idea is also tempting because I could create a cleaner (wire-free) and more robust cube. It also has the advantage that the cube would be made only by soldering LED legs together, as opposed to the MAX7219-based solution where I would have to find a way to make the cube more rigid by adding some non-conducting sticks between the planes, to hold them together. That would probably mean glueing.
What did you mean by "Lots of time available while watching millis() go by to update the 64 bytes that hold the array information." Were you suggesting that in the MAX7219-based approach needs a lot of time to fill up the registers?
You also wrote this:
"64 cathode drivers, and 8 anode drivers.
Can be done with 9 TPIC6B595 shift registers and 8 PNP or p-channel MOSFETs.
8 of the 6B595's will drive the cathodes.
Each bit of the 9th 6B595 will be used to pull the Base/Gate of the Anode transistor low to turn the part on, pullup resistor pulls it high to turn it off."
Is there a place I could find an exact wiring diagram for this? What about an example on how to program it?
As I wrote, I really am an amateur with high aspirations (the 8x8x8 LED cube). I'm struggling really hard to understand the answers you guys give me 
Because of this the MAX7219-based solution is more appealing to me. The chip takes care of LED currents, of multiplexing the LEDs. Also less components, less room for error. The only two problems with it are the price and the wires that would make the cube look less aesthetic... Because of this I'd like to try to understand the other solution too, with TPIC6B595 shift registers, but I need some diagrams and some programming example to see if I can work with it.
I really do appreciate your answers. Thank you!
Andras