This is more of a systems engineering problem than overcoming device physics though...
I agree, it's a systems engineering issue.
Your actual electronics implementation will likely be dictated by your physical requirements.
i.e.
how are you mounting and wiring all these LED's?
over what physical area are they spread? (e.g. all over your house for xmas lights, or just something the size of a table?
I haven't done any calcs but I'd start out with a basic configuration of X number of large PIC chips driving X number of LED's with a simple driving scheme (i.e 1 LED per pin), one board per bank of LED's.
Make each board identical, and possibly separately battery powered?
A large pin count PIC might drive say 50 LED's. That's only 100 PIC's and 100 boards for a system of 5000. Not much cost there, a few hundred bucks.
Each board has a DIP switch with an individual address.
Have one master controller board talk to all board on multi-drop bus system (i.e. I2C)
You could choose to have an individually addressed LED system, i.e. each PIC listens on the bus for a LED within it's range and latches that LED on.
Or you could offload more smarts to the remote driver PIC's.
In any case there are plenty of options depending upon how you want to program the system.
Do the costing for a simple system like that first and see were you stand and what limitations there are or areas for improvement in terms of system functionality or cost.
You might find you spend more money on wiring, connectors, mounting etc than trying complex schemes like charlieplexing to maximise the number of LED's per pin.
Beware the law of diminishing returns! (both in terms of cost and design time)
Sometimes the best complex systems take the dumb-arse brute force approach.
Dave.