Op Amp Selection Help for Rail/ Rail IO
Figuring out why the MAX4239 doesn't work for you is found in the datasheet.  There's a line in the table called Output Voltage Swing.  Since you're dealing with values close to your negative rail, you're concerned with VOL:

I think you're going to have trouble finding anything that swings less than 1mV.  This is because rail-to-rail output stages are built using BJT common-emitter or FET common-source circuits, which have a non-zero \$V_{CE(sat)}\$ and \$R_{DS(on)}\$ respectively.  As mentioned in the comments of your question, this is why you cannot achieve &quot;true rail-to-rail output&quot;.
So sounds like you're either going to need a bias or a negative rail to stay out of the saturation range.  One way to bias (out of several) is a technique highlighted in Chapter 6 of Analog Devices' free book called &quot;Op Amp Applications&quot; under Figure 6-117 which I've pasted below.

As for negative rails, they can be troublesome to generate cleanly if you don't already have one available.  One example of a solution is the LM7705 from Texas Instruments which is designed specifically for problems like yours.  However, this still might be too noisy for µV level signals so perhaps a bias generated from a tightly controlled voltage reference might be a better fit for you.