Do you have to be able to set an address for each LED? What if it's just a 2-wire communication where you shift data out to the entire string?
Take an RGB LED - $0.12 (1000 minimum)
with a WS2801 - $0.16 (1 to 1000)
1x 0.1uF cap - $0.03 (100 - 499)
3x resistors - $0.02 (100 - 499)
PCB - $0.72 (12 - I created my own through fab house)
And you end up with a pixel cost of $1.09 - multiply that by however many you want. Your Arduino just needs to provide a DATA and CLK source and you're done. You can either provide VCC/GND from the Arduino (3.3V up to 5.5V), or from an external supply.
Worth nothing: this is the exact same thing that many 5V addressable RGB strips are made of, except for the flexible and adhesive backing.