Not having a stable ADC reference is actually a symptom of a another problem in your circuit: you are not supplying a high enough voltage to the board. This is indicated by the 5V supply dropping to 4V and the 3.3V dropping as well.
The voltage regulator (MC33269D-5.0 IIRC) on the Arduino board has a dropout voltage of ~1.0V, therefore you need to supply it with at least 6V to get a stable 5V output. AA batteries start off at 1.5-1.6V and are almost dead at 1.1V so you must power the board with at least 6 AA batteries for a stable output over the entire battery life.
Powered correctly, you may either use the internal ADC reference or either the 5V or 3.3V lines. Since the temperature sensor varies by around 10mV per degree Celcius, you could use a voltage divider to set the reference voltage equivalent to the maximum expected sensor output voltage (e.g. for 50 degree C). This will give a more precise measurement.
If you want to use fewer than 6 AA batteries, try a DC-DC boost converter, e.g. https://www.sparkfun.com/products/10968. The linked example takes 1V - 4V and makes 5V. The output would be fed directly into the 5V pin of the Arduino, bypassing its regulator.
To get the board to run longer on batteries, put the MCU to sleep between sensor reads. The rocketscream low power library is great for this purpose. But it is only really useful when using an efficient regulator / DC-DC converter as the standard Arduino regulator uses 10mA just by itself!