A microcontroller is the way to attack this project. Programmers are not an issue. Many parts like the Atmel AVR can be programmed with a very simple circuit from the PC parallel port. Cost of doing this in a microcontroller will be X10 smaller than any other solution.
Since your update rate of the LEDs is so slow, I would use a serial to parallel converter chip outside of the microcontroller to hook up the LEDs. There are many, many, many possible chips to choose from. One chip dedicated to this job is:
**broken link removed**
Since this chip handles 16 LEDs, you would use two of them connected in a chain. Then it is just a software exercise to write the code.
If you do not use a microcontroller, then you are dealing with lots and lots of discrete logic chips. You will have to do all the counters and controls in hardware. Any bugs will require you to respin all the hardware. (With the microcontroller approach, most bugs are simple software changes.)
--- Steve