Ja ohne µC wirds wirklich schwer werden. Das steht dann in keiner Relation mehr
Ich würde dir also auch einen kleinen µC vorschlagen wie z.b. einen AtTiny2313 den du mit 5 Ausgangstransistoren ausstattest an denen deine Relais hängen. Dann noch einen Eingang wählen und schon kanns losgehen.

Softwaremäßig würde ich das einfach so realisieren:

generiere Zufallszahl zwischen 1 und 5
Prüfe ob Zufallszahl schonmal im Zyklus gekommen ist
Falls nicht:
Schalte entsprechenden Ausgang
Falls doch:
Generiere neue Zufallszahl
Speichere Zufallszahl um prüfen zu können ob diese bereits kam.
Verzögere 5 Sekunden

Fertig