Instead of using a resistor in series with the medium you are testing, to form a voltage divider, another technique is to use a constant current source [or sink]. Then, measure the voltage across the medium [or even, across the current regulator]--a voltage magnitude that will be directly proportional to the resistance in the medium. With a pure resistor voltage divider, there is a more math intensive inverse proportionality.
Also, with a constant current, you might be able to get away with a lower current, and still have a workable range.
Also, with a constant current circuit, it's easier to adjust the voltage range, and thus take advantage of such things as the internal voltage reference, for an increase of resolution.
It's still a voltage divider, but the current source/sink behaves like an infinite resistance. And, because the current remains constant, it can, perhaps [because I have no experience with sensors of this sort], be set to a level just below the electrolysis point, and it will stay there over the whole usable range.
If it's a current source, then the current source is the upper "resistor" [in the voltage divider], and the medium is the lower resistor. A current sink will be the other way around.
BUT, this probably is too expensive a solution for the OP. I guess it comes down to gain of feature vs increased cost.
Check out my Blog where I talk about Current Sources:
http://www.sinistercircuits.com/Blog/LEDs_LightemWithoutSmokinem/index.php#sec__current_source