Yes, sounds pretty plausible - you could use a capacitive bridge using the sensor and a fixed capacitor of roughly equal value.
join the two capacitors and connect to an analog input. The other lead of each cap goes to a digital pin via a 150ohm resistor, and you feed the digital pins in anti-phase. To centre the analog pin connect it to both GND and 5V via two 10M ohm resistors.
The amplitude and phase of the signal on the analog pin depends on the relative capacitance values. Code something like this might do the job (well I haven't tested this, so a pinch of salt advised):
void loop ()
{
digitalWrite (dpin1, LOW) ;
digitalWrite (dpin2, HIGH) ;
int difference = analogRead (apin) ;
digitalWrite (dpin2, LOW) ;
digitalWrite (dpin1, HIGH) ;
difference -= analogRead (apin) ;
if (difference > threshold)
digitalWrite (outpin, HIGH) ;
else
digitalWrite (outpin, LOW) ;
}