That CMOS circuit won't work if there is any switching noise on the DC rails (including ground noise). Any noise on the power rails will get coupled through.
As for the op amp circuit example, yes, that CAN work if you use low offset (<100uV), precision op-amps with bi-polar supplies so you can get down to 0 and 1 mV with your square wave. The op-amp has good PSRR and will have good noise rejection on the power supply.
I also gave it some thought, and I thought that a good way would be a switched 1 mA current source over a 1 ohm resistance to get 1 mV.
So I spiced it up here: (click for a bigger image)
The TL431, NPN transistor Q1 and R2+R3 act as a precision current source, sourcing 1mA over the 1 ohm R3,
giving you a precise 1 mV square wave that is minimally affected by noise coupled into the source. I've demonstrated
this by including a random noise source at the input which is over 100mV peak-to-peak.
The low pass filter RfCf at the input slows down the rising edge of the 555 output to remove some high frequency components, as well as offers a first line of defense at reducing some of the coupled input noise. You don't need the RC filter, and without it you will get some noise at the 1 mV square wave, but that noise is still very, very low at about 5 uV peak-to-peak due to the PSRR of the TL431.
The spice source is attached in the zip file.