How to control 500 individually addressable LEDS

Basically, for the project I'm considering doing, I want to have 500 LEDs controlled by an Arduino. They need to be individually addressable. Also, PWM capabilities for each LED would add much coolness to the project. They'll be in a matrix configuration, probably 25x20.

So my question is, would it be easiest to just use a bunch of shift registers linked together to control these, or is there a better way to control lots of LEDs?

Also, I could potentially use the concept of persistence of vision. This would allow me to only control say 40 at a time, and flash through every row/column quickly to make it seem like they're always on.

Anyway, I'm just throwing this idea out there to see what you all think would be best. I also don't want to spend a ton of money on this project.

You aren't looking at something that will be very cheap AND robust enough for what you want. Take a look at the LED Coffee table tutorial made by SparkFUn
Basically they took a bunch of RGB LED Matrixes and linked them together. Each one of those matrixes is about $60, so do the math there.

But you can do all sorts of cool and neat things with it, like play pong.

Sounds like a Peggy 2... 30cm square 25x25 array of LEDs

http://www.evilmadscientist.com/article.php/Peggy2

About $200 for a full kit (that's about $90 for whopping big PCB, $100 for 625 LEDs, and $10 for chips.) Also all open source, and uses the same CPU as an Arduino, so you could just copy the bits you want...

Well, they're using over 4000 LEDs and I'm only planning to use 500. I think with a combination of POV techniques and shift registers it shouldn't be too expensive.