The VGA video generation is performed by the PIC counting cycle by cycle.
At 20MHz the PIC executes one instruction cycle at each 200ns. It means that a whole VGA line (31,77us) shall last 159 cycles. This value is rounded up but close enough for a stable image (full detail)
The VGA output is impedance and amplitude controlled. It can be achieved by doing some math. The values are not critical, though. Anything about 20% of the calculated values are good enough.
The randomness is generated by using a Galois LFSR (Linear Feedback Shift Register) with a different seed for each line of 8 'dots'. The code was borrowed from PICLIST.
The timing for colour changing is done counting frames on the last blank line of a screen. The interval time is formed by adding 22 with the 4 least significant bits of one of the random variables used to control the colour of the dots. This results in a time of .36 to .63 seconds for each change.
And that's all.
Do you have a lot of spare clock cycles? I'd love to do this with my collection of 12f683. They have 5 general purpose GPIO which should be enough, but then it would require to run off the internal oscillator. Not sure if the accuracy or the speed (1MIPS) would cut it.