Thank you again for your help, guys!
I'm thinking and thinking an thinking about which approach to take, but it seems that the more I know, the more confused I get :)
I must admit, the solution that appeals to me most at this time is to have 8 separate, unconnected layers, each driven by a MAX7219. It seems that the current consumption is not so bad after all and I'm hoping that the ones I can find on ebay (10 pcs for 5$) will do the job. I would not divide the LEDs into 8 layers the conventional way though. Instead of having the usual 8 horizontal layers, I'd have 8 vertical layers. This has several advantages: 1. Having 8 layers driven each by a MAX7219 requires 8x16 wires. Half of these would be connected to the layers directly from the bottom of the cube (because the layers would be placed such way that half of the required wires would face the bottom). This means that only 64 wires would be visible. These could enter the cube from the back of it (the side which is away from the viewer). Could still be messy... 2. By having these vertical plane layers, the weight of each layer would stand on the bottom 8 LEDs, so I would have to add just a few non-conducting sticks to strengthen the cube, maybe just at the top and around the middle, not everywhere. I'm not sure if this would look nice because the cube would be more transparent or it would look weird...
I guess the main reason why I'm trying to convince myself that the MAX7219-based solution is best is because it's the simplest from more than one perspective: A. Less components to solder in the circuit. B. Takes care of LED currents and even can be used to set brightness from software easily. C. The software does not need to be aware of the multiplexing, the Max chips do it themselves.
Searching the Internet I have found that somebody has actually pulled it off with this Max7219-based solution applied to a 8x8x8 LED cube (http://hackedgadgets.com/2011/09/02/8x8x8-led-cube-powered-by-an-arduino/). Unfortunately, I must say that the result is not nice at all. I mean, I do respect his work, but let's face it, the usual LED cubes that we see are much more better looking. Those wooden sticks at the corners of the cube block the vision a lot and those wires at the back are just plain ugly. I'd hate to turn up with a result like that after who knows how many hours of work.
I've never thought it would be so hard to build a LED cube. There are solutions for every problem related to it, but none of the solutions is "perfect". You can only get some benefits by sacrificing others... I'll try to think of solutions to go for the MAX7219-based solution and to get rid of the ugly wires and to solve the problem of non-conducting sticks between the layers. As much as I realize that most of the cube out there don't use this solution because of the disadvantages I have just enumerated, I don't dare to try the other solution. It just has too much room for error both in building the circuit and in the software part which gets more complicated by having to implement multiplexing. Also it's less foolproof. If the software messes up the multiplexing and lights up all the 512 LEDs, I don't know what's going to happen...
Like I said, the more I think of it, the scarier it gets... :)