I don't see PWM on the STP16DP05..? I was thinking of using the TLC5940 - already ordered a couple to experiment with.
Ah, the venerable TLC5940. I killed a lot of those in my youth.
I know about smart LEDs but as you said, that's cheating - what will I learn from that?
Only cheating on the soldering side. Getting it nice and square is still a challenge and the programming will still be difficult.
Watch this before deciding:
And ... updating 512 of them at a decent frame rate will be interesting - for 30Hz you'll have to split the cube in two and update each half separately. Maybe even four parts (I can't be bothered to do the math...) with an individual Arduino for each part.
PS: Don't underestimate the power requirements. 512 LEDs set to RGB(255,255,255) is 30 amps
(And probably too bright to look at...)
Multiplexing helps with power, but...watch that video again before you think power is a good enough reason.