Mondomatrix makes some serial (rs-485) addressable LED driver boards, and is based on the Arduino platform: http://www.displayduino.com/ You might be able to put together a system using that hardware fairly easily

Dedicated driver chips with serial interfaces will indeed probably be the best route. Dealing with individual shift registers will probably mean a very complex circuit. At least Maxim and TI make some. I don't remember if either has a model particularly suited for that much.

It will still take a lot of hardware.

As for power, programming, and buses, the datasheet for each driver will probably have most information you'll need.

XMOS uses the Macroblock MBI5026 with their LED tile kits. I think that they are used in most other professional systems.

Leon

Check out "LED driver" ICs on mouser/digikey. TI, for example, makes a bunch of drivers with a variety of interfaces (I2C, SPI) that would certainly meet your needs. Most of these drivers are designed to be daisy chained so the serial out from one is fed into the serial in of another.

For example, something like the TLC5940 offers 16 channel PWM control. So, basically it's a constant current 16-bit shift register with 12-bit grayscale PWM control. I can recommend that particular IC as I helped design an 80x16 display with it.

I've no idea of the range of PWM you need for an LED but I've been working on a 64 channel PWM controller for a servo control application that can give me pulses of between 600us and 2.4ms. This uses CD74HCT238E's (3-8 line demultiplexors) to generate 64 channels from 8 I/O pins on an ATMega168 and is controllable via simple serial commands. I guess you could chain multiple versions of a modified version this controller together on a serial line and address all 500 LEDs... You could probably use the ATTiny2313 version of the controller as your firmware requirements would be simpler.

My blog contains the assembly source and schematics and details of the design process.

What layout do you want the LEDs in? You can save a lot of work if you buy some LED matrixes, you can get single-color 8x8 LED matrixes (64 LEDs) for a buck or two.

You're not gonna get real PWM with an AVR and shift registers on this many LEDs, but you may be able to squeeze 2-4 levels of brightness. You'd have to run the numbers and see what's possible.

Allegro makes some handy constant current sink shift registers specifically designed for controlling arrays of LEDs, so that you don't need the extra resistors, that will make things simpler as well. You might not be able to drive the LEDs directly from the AVR output if it can't provide enough power, so you'll need to use transistors. You can get them in arrays in a single IC, that saves some work too.

Just copy :-)

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

the "peggy 2" version is, IIRC, Arduino friendly ...