Requirements:

1) 4 RGB LEDs - I'm using common anode, but it'll work with common cathode.
   Just differently.  You'll have to map out the pins and colors differently.

2) ATtiny85

Procedure:

1) Build a RGB spire per Asher Glick's Charliecube:
   http://aglick.com/charliecube.html

2) Hook the spire up to the ATtiny as follows:

Pin 5: Lowest common (anode/cathode)
Pin 6: Next highest common (anode/cathode)
Pin 3: Next highest common (anode/cathode)
Pin 2: Highest common (anode/cathode)

ATtiny pinout will be as follows:

Pin 1: Reset - wire to a pushbutton for easy resets, ignore otherwise
Pin 2: LED 4 common
Pin 3: LED 3 common
Pin 4: GND
Pin 5: LED 1 common
Pin 6: LED 2 common
Pin 7: NC
Pin 8: VCC

It runs nicely off of 3xAA batteries.  Appropriate resistors on all the common
pins if you feel they're necessary.  (I do, some people don't.)

------------------------------------------------------------------------

BOM: (prices are volatile)

1x MCU: http://www.dipmicro.com/store/ATTINY85-20PU ($1.56)
4x 10mm RGB Common Anode LEDs: http://www.dipmicro.com/store/LED10AD ($2)
1x 3xAA Battery holder: http://www.dipmicro.com/store/BH2465 ($3.21)
4x resistors - mine are 1ohm! But 47 is probably more reasonable