Patchwork style render

Hey JGO (long time no see!),

I’m trying to figure out how i can generate some kind of ‘patchwork’ style pattern image that will be infinite.

Kind of like this picture except each field would be a totally different colour

http://vrap.co.uk/760_wm.php?src=img/760_4391.jpg&p=86

I’ve looked into Voroni diagrams but an infinite implementation, although seemingly possible, strike me as inefficient and not very mathmatical.
Perlin Noise doesn’t really do the job either, as this would make it more likely for certain colours to be connected which I don’t want, I want complete randomness.

Any ideas on the best way to go around this?