adjustable time delay, random output
Especially if you actually need a display of sorts, but even without, this sounds easiest when implemented in a microcontroller.

You don't really need anything fancy - watch for your  button input to go high (or low, depending on how you wired the button). Wait. Toggle output pin. Wait. Toggle again.

On that output pin, you'll need some transistor and a flyback diode to switch the 12V for your relay. There's inexpensive N-channel MOSFETs that integrate the diode and can directly be driven with logic levels.