It's a pity the LM3909 was discontinued as it provided a vastly superior means to achieve what this circuit does, not least because it was capable of flashing a 2V LED from a 1.5V battery (and make it last for years), whereas this circuit requires an almost preposterous 12V supply to do the same. Nonetheless, it's interesting in that it makes use of a transistor characteristic that rarely gets used in practical designs.
Modifying it to add the features you want, however, is not going to be at all easy without an IC because of the obscure way it operates. You could add the fade up and down using an integrator, which would be trivial with an op-amp, although given long enough you could implement it in discrete components, but the random element is much harder. All electrical components generate a small amount of thermal noise, which you could amplify to the level where you could sample it to control the delay of a monostable; once the delay expires it would trigger the LED pulse, sample a new noise figure and trigger itself again with the new delay - but with discrete components this is going to be quite a task.
Or you could admit defeat with that route and use the smallest and cheapest microcontroller you can find, such as a PIC10F200, and use an output pin to drive the LED. By turning the LED on and off quickly you can control its brightness and you can implement a pseudo-random sequence to provide a variable delay. All you would need would be a 3V battery, the PIC (which my usual supplier sells for £0.34), the LED and a resistor - and it would be a great learning exercise.