You can increase the effective resolution by intentionally oversampling the input signal. Here is brief summary of the idea from an application note on the topic provided by Atmel:
The theory behind ‘Oversampling and decimation’ is rather complex, but using the method is fairly easy. The technique requires a higher amount of samples. These extra samples can be achieved by oversampling the signal. For each additional bit of resolution, n, the signal must be oversampled four times. Which frequency to sample the input signal with, is given by Equation 3-1. To get the best possible representation of a analog input signal, it is necessary to oversample the signal this much, because a larger amount of samples will give a better representation of the input signal, when averaged.
The full application note can be obtained here: http://www.atmel.com/images/doc8003.pdf.
In your specific case, you would need to sample at about 8KHz to get the equivalent of 16 bits of resolution out of your 12-bit ADC.
Here's how I arrived at this number:
f_oversample_rate = f_current_sample_rate * (4 * (desired_bits - current_bits))
f_oversample_rate = 500Hz * (4 * (16 - 12))
f_oversample_rate = 500Hz * (4 * 4)
f_oversample_rate = 500Hz * 16
f_oversample_rate = 8KHz