As I posted in the other thread, a microcontroller could do this with more apparent randomness* than a simple logic gate device. An 18F1320, 8 LEDs, 8 resistors (330 ohm) plus power supply & decoupling would be the minimum. I suggest the 18F as it's dead easy to write a program in Swordfish BASIC SE that would use the random module available for that compiler.
*Not easy to get true random numbers in a digital world...
PS an example of what you mean by delays, random etc would help. Like stars flickering?