A subsystem with randomised outputs (no microcontrollers)
Four possibilities spring to mind:


Your idea of an astable connected to a 4017, might just work, if you use


A trigger pulse of 1000 or more times the period of the astable oscillator (possibly using a 555 monostable to extend the existing trigger pulse)
A thermistor, governing either the frequency of the astable oscillation, or the length of the trigger pulse.


In this case, the tiny random heating/cooling of the thermistor by air currents may be sufficient to produce a random result.
If this doesn't work, a microcontroller is the easiest option (this is probably true even if you have no experience with microcontrollers).
The kind of algorithm that would be implemented inside a microcontroller can be built out of 4000 series logic, but it would not be entirely straightforward. With a handful of shift registers and XOR gates you can build a linear feedback shift register (LFSR), which produces a pseudo-random bitstream. You could demultiplex a few bits of the shift registers to enable one of N outputs (easiest if N is a power of two). You may need to clock the LFSR more than once per output, to avoid strong correlations in the random output.
If you actually need a genuine source of randomness, one low-cost option is to use transistor avalanche breakdown noise to generate a random bitstream, and then use a shift register and demultiplexer again to generate the random one-of-N output.