I have a microcontroller (ATmega328) powered by a single cell lipo battery. I would like to make the microcontroller know when the battery voltage gets under a given level (someting around 3.5V) to output some kind of "low battery" alert. Can I do that without using another battery? Does the internal analog reference remains stable if the power supply voltage changes? If so, can I simply connect the battery positive terminal to an ADC pin and output the alert when the reading gets under a certain number?
The Atmega328 has both Power on reset and Brown-out detection build in. You don't need to add any components.
Read the datasheet: http://www.atmel.com/Images/Atmel-42735-8-bit-AVR-Microcontroller-ATmega328-328P_Datasheet.pdf
Read Section 15.2 and you will understand exactly what voltages will stop the microprocessor from running by activating reset.
If you want an early voltage level detection with an indicator (while you processor can still run code), simply use the onboard A/D to provide the measurement.