You need AC excitation and stainless steel probes. If you stick to the two rod design, 4 or 5 mm rod clamped in a large 'choc block' connector would do for a cheap probe. A better quality one would involve threading the end of the rod so the connection can be made with two nuts, a shakeproof washer and a crimp ring terminal, then potting that in epoxy. Connect a resistor between an Arduino PWM pin and an ADC pin, and from the same pin, a large non-electrolytic series capacitor to one side of the probe, then the other side of the probe via another capacitor to Arduino ground. Set up the PWM for a squarewave of several KHz frequency. The ADC sampling must be synchronous to the drive signal, ideally just before the PWM goes low, but in practice it should be OK to sample it immediately after it goes low, so triggering it from the PWM ISR would be possible. A better option would be to use ADC auto-trigger on timer rollover, set the pin by compare match, and reset it in the ADC conversion complete ISR.
A pure hardware solution would use a quad OPAMP or comparator - one section as an oscillator, driving a bridge with the sensor capacitively coupled as above, then the signal processing depends on whether you want an analog or a digital output - either stretch the pulses so it stays low for a whole cycle of the oscillator if the soil conductivity is high enough, or a precision rectifier and low pass filter circuit for analog output.