Here is the basic idea:
V1 is the filtered PWM output and R2 is your sensor. U1 is voltage to current converter, with current through the load R1 being I = V1/R2. This means that voltage across R1 depends on both inputs. U2 and U3 is an instrumentation amplifier with gain 10, which amplifies the voltage across R1.
With R1 = 100 Ohms and V1 = 0..5V the circuit works for R2 = 50..5000 e.g. across two orders of magnitude, which from what you say should be enough.
What you do is take out and compare it with reference voltage (4V would be appropriate here for maximum dynamic range) and use successive approximation on V1 to get out as close as possible to the reference voltage. From V1 and known voltage drop across R1 (e.g. reference voltage) you can now calculate value of R2, your sensor. This will of course get you result only within the resolution of PWM, but you can use second instrumentation amp to amplify the error (difference between out and reference voltage) to get it within the range of your microcontroller's ADC and this will get you additional bits of resolution.
You need two opamps (U1 and comparator) and two instrumentation amps. Use real ones instead of making them from opamps, because the imprecisions of resistors and opamps will introduce error.
If two orders of magnitude were not enough, you can replace R1 with digital potentiometer to get another degree of freedom. I have never worked with one, so I don't know how precise they are and whether such solution would need some calibration or not.
Also, I should mention that it was jpc who came with the idea.
UPDATE:
Ok, I have to agree with OP that this is not really the the answer to his question (though it solves the problem technically). I allowed myself to be carried away by "adaptive amplifier" in the title as an excuse to do some analog design. Forget everything writen above, unless you want to learn something (little) about opamps. Here is, I hope, better answer and much simpler solution:
Use resistive divider powered from a voltage regulator (to separate it from other circuitry's noise), with upper resistor set to about the maximum resistance your sensors can have (Rmax), and with the lower resistor being the sensor.
Set the reference voltage for your ADC to half the voltage regulator's output.
Then you sample the voltage on the sensor with your ADC. This way you need only one single-ended channel per sensor. I made ADC recommendation in the other post.
If you use 10 bit ADC that is integrated in the microcontrollers you mentioned, you will not get much of a dynamic range, though. Enhancing the range using analog circuitry, like the one I originaly posted, would add too many additional parts, which is why I would recommend simply to use some 24 bit ADC, like the ADS1256 I recommended in the other post, because it will give you low noise and high dynamic range, in a single chip (plus the reference, which is tiny, and the voltage regulator, which can be also tiny - you can also try to leave the regulator out and power the resistive divider directly from the reference - this will rob you of 1 bit of resolution, but there are plenty of them anyway). You will have to do some number crunching ("Auto-calibration by finding min and max values in a given analysis window" - is a good idea), but that's easy in this case.
I hope this is little more usefull.
UPDATE 2:
This is the last one: I have been going through MSP430 microcontrollers from TI and I have found that some of them have 16 bit sigma-delta ADC with internal reference. Namely MSP430F2003 and MSP430F20013. That would be your one chip solution if you are willing to give up on Atmels. Very low power too. And they have in queue microcontrollers with 24 ADCs, but these are not in production yet. Than there are also PSoC microcontrollers from Cypress, which have 20 bit sigma-delta ADCs (PSoC 3 and PSoC 5 series), also with reference. These would be even better.
On how capacitative touch "works", have you had a chance to read through the CapSense library page on the Arduino Playground? It's a decent overview. The technique is typical - measure how long it takes to "charge" a metal plate up to some voltage through a known resistance and infer the capacitance from that time interval. There's also a very instructive lab exercise at Cornell's microcontrollers course website.
What are the physics going on here? When you bring your hand closer to the plate you are increasing capacitance (by narrowing the distance between "the plates") - see also wikipedia entry on capacitance. You kind of serve as the plate of the capacitor connected to GND. So yes in principle driving an actual plate to GND through a transistor could work. Furthermore, if your Arduino is plugged into the wall, you most likely don't need to worry about whether you're at "the same" GND, it will be close enough. You might have a slight issue if you're Arduino is battery or USB powered though.
As for the actual circuit. I would actually try just connecting an actual digital pin to the plate. When you want to simulate "no touch", turn the pin to an input (without internal pullups enabled). When you want to simulate "touch" turn the pin to an output set to LOW. The only reason for using a transistor is if you have a current demand that exceeds the rating of the pin (about 40mA I believe), and this case really doesn't qualify.
Best Answer
For capacitive sensor check PIC12F1822/23 from Microchip. You can also try an accelerometer as sensor. I created some device, connecting analog accelerometer module to ADC input MC and it senses even light touch. Also you can try some barometric sensor or electret microphone. It will sense pressure change from air move. Active sensors, like ultrasound and laser may not fit your application because they have dead zone. Infrared sensor like AD8833 can be useful too, but it needs processing image.