I disagree with many of your assumptioms.
- MAX7219 multiplexes 64 digits. It has no more than 8 LEDs on at a time, thus not much more than 160mA if 20mA/LED is being used.
Additionally, 5V/4A supply is easy to find - I use this one in several projects
5V 4A Power Adapter OPENPEAK OP-20004
For my 8x32 display using 4 of MAX7219 and a Duemilanove, a 9V, 1A supply was used, drawing under 1A of power as all 5V current went thru the onboard regulator. - More components, yes, but easier to assemble LED cube as all columns are connected, and all Layers are connected, thus just 8 wires need to be hidden away. With non-multiplexed MAX7219, need isolated layers and 16 wires per layer.
- MAX7219 is $1.25/chip from taydaelectronics.com. TPIC6B595 is 83 cents from avnet.com, plus PNP or P-channel MOSFETS. Seems comparable when totalled.
- Agree with you on wiring. Don't know how you solve the cube stability while maintaining layer isolation.
- There are many examples of LEDs cubes. The soldering together is less tricky than you think, there is just a lot of it. Here is one of the best writeups I have seen.
http://www.jameco.com/Jameco/workshop/JamecoBuilds/4x4x4ledcube.html