Ignacio,

Instead of the LM35 sensor I'd recommend the LM75 sensor with an IIC interface, you'll get the digital temperature value so you don't need the analog multiplexer anymore.

But please have a look at the DS2438 chip in a dip-8 package (the cost is about $1.2). It can measure a temperature over the range of -55 to +120 in 0.03125 increments and it can measure a battery voltage by 10-bit internal ADC as well.

Hope it helps.

Regards,
George