While building a random LED flasher from discrete parts is possible, several low-cost integrated circuits are available to make the project easier. The 555 timer, available for under 25 cents in 2009, is a handy building block. Many LED-flasher schematics are available online for it. If you write software, a programmable integrated circuit (PIC) can do the job. Flashing patterns are determined by your program. You can also create pseudo-random patterns with a simple circuit based on the 4026 Counter/Display Driver IC.
The 555 timer, or its cousin, the 556 dual timer, have long been mainstays of the hobbyist's workbench. To make a random flasher for any number of LEDs, you'd need one 555 per LED, or one 556 for every LED pair. In addition to this, you'll need a set of three capacitors and three resistors to set the timing for each LED. Depending on the timing you select, you can set the resistors and the capacitors to one value, simplifying your purchasing. To create a set of randomly flashing LEDs, simply build a set of identical 555 driver circuits, each with its own "on" switch. When you turn them on, they will blink on and off out of sync. Turning them off, then on again, will create a new pattern.
PICs can perform sophisticated tasks, given the right software. You'll need the PIC itself, the PIC programming hardware and a handful of outboard parts, including LEDs. The programmer connects to your computer, where you develop the programs. In this case, it's the programming, not the hardware, that determines the flash pattern and speed. If you have other projects that could also use an intelligent controller, investing in a PIC set-up makes sense. If your LED flasher project is more of a one-time thing, you'll want to look at other options.
The 4026 combines a counter and seven segment LED driver. The seven-segment outputs plus a divide-by-ten output will drive eight LEDs. While the flashing will not be strictly random, when the lights are properly arranged, they won't have a discernable pattern. This circuit needs only the 4026, a 555 timer, LEDs and a few passive components to make it complete.