I think that two gain programmable instrumentation amplifiers is an interesting idea. It is the first thing that came to mind.
I think you can keep the very high CMRR the instrumentation amplifier has, the problem goes to summation of gain differences and offset differences.
If you use a chopper stabilized fixed gain of 10 or 100 instrumentation amplifier (2x) you might have a viable solution. The offset will be in the nanovolts and the gain should be matched very well since it is trimmed to 10 at the factory. This of course lowers your op amp choice very much however.
Maybe you can use high resolution DACS (4 of them) to match the offsets and gain of two gain programmable instrumentation amplifiers too. I believe they are just programmed by a resistor which biases some kind of control system inside of them, it might be replaceable with a DAC.
If you use dual output DACS you have thermal stabilization of the biasing of both op amps.
You could use some seriously high speed shit if you did it this way (I believe they have some fairly wide band gain programmable instrumentation amplifiers.) The chopper compensated ones will of course have low bandwidths. And you would not be at the mercy of modern low voltage op amp supply rails
