Could you use the blink without delay example with an interval generated with the random function?
http://arduino.cc/en/Reference/RandomSeed
http://arduino.cc/en/Reference/Random