I'd not like to ruin your learning fun BUT if you get a more or complete idea on this project you can move on to more difficult ones.
The circuit below is almost exactly what immediately came to mind for me (I have had lots to do with 4017's in recent years :-) ) and lo and behold somebody has done a very nice job of writing it up.
The 4017 is a decoded "Johnson Counter" (look it up) which provides a sequencing one-of-ten output.
You can cause it to
count up to position N and stop,
or to position N and then reset
or you can chain chain several together
or more ....
A very useful IC.
Datasheet for the basic CMOS version here
and for the buffered 74HC4017 version here.
Note that the "basic" CD4017 has a very special feature which tends to be lacking on all "improved" versions - it has a Schmitt triggered clock input - which means that you can use it with a user pushbutton input or other slow and noisy input. ometimes an immensely valuable feature.
The circuit itself is enough:
Does this do whta you want?. Well, almost.
Look at the enable and reset lines.
Look at the datasheet.
What happens if you plug the enable line into output N?
https://homepages.westminster.org.uk/electronics/images/4017_08.gif
BUT they have done a really superb job of presenting a plug in bread-board version here
Leading to this. You could use one small breadboard and less LEDs and a different oscillator
(eg 555 / 4040 et al etc) but this is an extremely nicely done example
THEN you can consider a zillion alternatives [fromhere] - all images hotlink to a page. Look at he top of the page to see the obvious and extremely useful way that I got this eggtimer circuit collection and this overlapping but not identical egg timer circuit collection (plus some other stuff in each case).
74HC4017 "under the hood":
Clock accuracy:
Try it and see.
Use a good quality clock cap- NOT a ceramic.
What if you clocked it twice as fasts and used eg diodes to OR a single LED per 2 outputs?
Or 3 times as fast?
If you want to use a faster clock look at CD4040, CD4020, CD4060. Note that one of these can both divide and self oscillate. You can still have 2 ICs total but a clock and a divider as well. Enjoy.
Since this is for a real world application, not a hobby project or a school assignment, the requirement not to use a microcontroller is just silly.
A micro is the obvious and easy way to do this. A very small micro like a PIC 10F200 could do this, but since this is also apparently a one-off there is no need to economize. Something like a PIC 18F2520 would be easy. That's way overkill, but the extra $3 or so will be made up with easier programming. This part has a internal RC oscillator, so you pretty much feed it power with bypass caps and it can run.
I agree with Wouter in that relays are appropriate for this since it's a one-off and you are switching very slowly. One DPDT relay is used to set the polarity, and a second SPST is the on/off switch. Now you only need circuits to drive the relay coils from two digital output lines from the micro.
Best Answer
A small microcontroller is the most appropriate choice for this. Yes, it's possible to create a random analog circuit, or latch a high-frequency counter to create a random digital value, but it's going to be more fiddly and many more components than you want to deal with.
Any MCU will happily do this. I'm guessing you are not very familiar with microcontrollers, and therefore I would recommend an Arduino due to the large volume of community support and existing resources.
If you really want to do this with discrete logic, use a ring oscillator (high frequency) to drive a small counter. When the button is pressed, latch the value, load it into a downcounter, and start the downcounter. When the downcounter reaches zero, the lights go off.