The problem, I tend to bite off more than I can chew and I know very little about electronics, programming or pcb design
Then I would really suggest you build something else first. How about a 3x3x3 cube, that way you will get a little acquainted with LED's, soldering/building, IC's that might be handy for multiplexing and programming the thing (even if a 15^3 is another beast than a 3^3).
Also, you would only need 27 LED's (or 30, a couple of extras is nice to have), and don't have to buy 3500-ish as the first thing you do. A mere 1% of cost and work for a test run. Even if including an Arduino, I think - 3500 LEDs isn't cheap?
One important thing, if you really go through with this I would suggest choosing diffused LEDs, not LEDs with clear lenses. Reason being the diffused ones are more visible from a broader viewing angle. I couldn't find any reference to whether or not the ones you found are diffuse or not. Would be a bummer buying all those LEDs and having to sandpaper 3375 LEDs by hand....
Btw, have you seen this 16^3 cube? Really awesome! But I don't know whats powering it (page wouldn't load atm):
Also I don't know how feasible a 15^3 cube is with an arduino.. maybe one of the bigger ones, like the
Mega, or a
Sanguino. Or use two or more arduinos maybe. Just some loose suggestions.
Also you'd need to decide if you want PWM ("grayscales") and/or RGB

But given the size I think not!
As for your questions:
• individually is certainly not a option!
• is multiplexing the way to go?
If not the one then the other, yes. And I'd agree that individually (as in all of them simultaneously) is not an option. Then you have to decide upon some multiplexing scheme.
• are there other options available?
Nothing that comes to mind now.
• Is it possible to light all 15^3 at once?
If you use some kind of multiplexing, then not really. But:
I have commenced research on multiplexing and the concepts behind it and how it works and why it is used
You should know about the effect of POV then? POV - persistence of vision. IE provided the framerate is high enough, you could make it seem like they are all on at once.
* What components are required to make that happen?
Not really easy to answer..sorry. There are quite a lot of options. I'm sure you have seen lots of threads mentioning things like shiftregisters, to TLC5940s, ULN2803 etc... I don't really dare give advice on your mega cube! But at the very least some transistor arrays (like ULN2803 or similar) and / or transistors to drive the cube.
* What are the power requirements of such a cube and how would I meet them?
...and a hefty power supply!
Power requirements for just the cube will depend on what multiplexing scheme you choose.
Lets say you manage to lit an entire layer (15x15) at once, then this is the power requirement (+ logic circuitry and the microcontroller etc). This multiplexing would then light each layer in the cube for 1/15th of a frame time. Since each LED is also lit like that, you could overdrive them somewhat to get it brighter.
Lets say one LED use 20 mA as standard, but you drive them with 50mA (this is for 1/15th of a time - btw I choose this as an arbitrary example). Then one layer (and also the hole cube sans logic circuitry) would require 225LEDs * 50mA = 11.25 Amperes, at whatever voltage you use for the LEDs.
Does the ability to light up all LEDs simultaneously require multiple multiplexes (such as 7 x 83), which would physically operate separately, but visually as one?
Not necessarily, but maybe in your case because of the size. If you do, take care that they are syncronized and have the same frequency, or else you might see flicker. Shouldn't be a problem if you control it all from the same microcontroller.
Btw with multiplexing not all of the LEDs light up simultaneously, but if done fast enought, the eyes wont notice (POV again).
I am really going to need help/advice to realise this project. I hope a few of you take pity on this fool and help him on his way.
There are some really nice and talented people here, which usually answer specific questions, but nobody will write the program for you (for free, anyway. Unless you are really lucky

But whats the fun in that?)