Simon Says without Microcontroller
Generally to generate "random-ish" numbers in hardware (for amusement-grade purposes), you can do something such as take a mechanism which is somewhat unpredictable and combine it with a mechanism which is predictable, but not obvious.

For example, if you have a counter running quickly, and sample the output whenever the user presses a button (such as while playing back the previous sequence) that will be somewhat random, since they may take varying amounts of time.  But someone gaming the system by pressing buttons very quickly might tend to get the same few values over and over again (though if the clock is in the MHz range that may not be a realistic concern).

Conversely, you can use a Linear Feedback Shift Register (Wikipedia) which feeds a combinatorial function of the current state a shift register back into it's input, to generate a sequence that is not readily obvious to humans, even though its output for the same inputs will actually be entirely predictable.  Used by itself, this wouldn't be a good idea either since it would give the same sequences every play of the game and so quickly be memorized by a repeat user.  

But, if you combine two methods, such as using the timer to get an unpredictable starting value, and then using the linear feedback shift register to mix it up (or perhaps letting the LFSR free run against a fast clock, and sampling it based on user interaction) you should be able to get something random enough for an amusement game.

Another source you could try would be the low-order bits of an analog-to-digital converter.

Whatever you do, you'll probably want to simulate it (and your overall system design as well) before you build the circuit.  The project is complex enough that using a small FPGA or larger CPLD may be worthwhile.

And finally keep in mind that historically, the original Simon game apparently used an early microprocessor, the TMS1000.  Generally complex sequential operations can be more efficiently implemented that way, with state machines chosen only for problems which are simple, must run extremely fast, or are learning substitutes for eventual work on such problems.

Edit:

http://www.waitingforfriday.com/index.php/Reverse_engineering_an_MB_Electronic_Simon_game

Contains some interesting observations, including an eventual change from the TMS1000 to what may be a custom labeled version thereof.  More relevant to your question, it suggests that the original generated its random numbers by sampling a free running counter when the user pressed a button ;-)