Best way to determine if a 5 gallon water jug is getting empty
Using a Force Sensor to Measure a Quantity of Water

To satisfy your requirement of having the sensor on the exterior of the water container, I would recommend using a force sensor to weigh the bottle at set intervals. A force sensor, such as the FlexiForce A401, is a type of resistor that changes resistance in response to the amount of force applied. While not as accurate as a scale, it should provide enough accuracy (+-3% according to the datasheet) for the application described.

The basic procedure would be to hook up the force sensor to the Arduino and first measure the resistance with an empty bottle, then measure again with a full bottle. This will give you an idea of the force that your specific platform is actually applying to the sensor, and you can then fine tune the voltage (as per the datasheet) for your installation. 

A basic tutorial using a similar force sensor with an Arduino can be found here.

Other Possibilities


Optical Liquid Level Sensors
Ultrasonic Level Monitoring
Thermistors and Heating Coils at various levels to Measure the Thermal Mass (i.e. water) near the Sensor