Just to clarify, I think 230nV was a typo - it's corrected in #9 as 23uV. Easier, but still not trivial!
I'm no design engineer, but I think you are on the right track looking for "instrumentation amplifiers". Although you can build an instrumentation amplifier from single op-amps, as far as I can see this would be a typical application for one of the many purpose built instumentation amplifiers that are available, like the AD634 that you have already mentioned.
For the sake of throwing some ideas about, I think I would do the following:
1. Use an instrumentation amplifier which uses an external resistor to set the gain. In this aplication I think DC acuracy and drift would be your biggest concern, so you can trade off other atributes against these.
2. Use reed relays to switch in different gain resistors under the control of the microprocessor. Design in more gain steps than I think I might need and make it easy to change resistors so the gain steps can be adjusted. Relays are slow, bulky, expensive etc, but I think they should give you the best chance of avoiding noise injection, offsets caused by leakage, gain problems caused by on-resistance, nonlinearities etc. Something of a safe option.
3. Provide some RC filtering on the output of the instrumentation amplifier, but nothing active to avoid introducing any other noise or inaccuracies. This could probably be set quite low in frequency and should remove quite a lot of noise.
4. Use an external ADC (rather than one built into a microcontroller), so that you can select the best one for the job and lay the board out in an optimal manner. I would rather select an ADC with more bits of resolution than I could use than one with too few. That is to say, I'd rather have the amplifier noise determine the dynamic range then the converter resolution.
5. Use software averaging across multiple reads of the ADC to further reduce noise.
6. Have the software compare "before" and "after" readings from the ADC when switching gains, and calculate the gain change of the amplifier from this. This can give you some proof that the amplifer is working correctly, and should allow you to avoid "glitches" in the readings when the gain range switches.
This is just some of my thoughts - I'm sure there are some people more knowlegable than I who'll be able to point out what's wrong here and give some better ideas.