I've just built a 4x4x4 cube recently, the way I did it was 16 columns, and 4 rows, which required 20 pins. A 5x5x5 cube could be made with 25 columns, and 5 rows, requiring 30 pins, but thats too many, so multiplexing wont be enough to do what you want.
You could charlieplex the cube, which would reduce the number of pins enough to work, or you could use some shift registers or LED drivers to get the pin count low enough.
charlieplexing wont require more parts, but it will make it a bit more complex, and difficult to build.
When i upgraded my cube, I added 2 shift registers (parts cost less than a buck), and now Im using about 1/2 as many pins.