What about using a pseudo random counter - see attachment.
Do you want to be able to control the times that the lights change?
Or do you want it to be free running?
You would need some gates to be able to turn on each light individually.
The pseudo random counter can be made longer or shorter.
The 4 stage shift register will give you 15 states.
So, for example, if you had 5 lights, then the gating could be designed such that light 1 is on at counts 1, 7 & 11.
More states will make it appear more random.
If you want to be able to control it from the supply end of the 2 wire connection, then you could apply some type of modulation on the DC.