Low current, long life batteries with an extended temperature range?
You'll have to do some searching to find exactly what you want, but it's out there.  For example, here's a link to some Panasonic batteries that work from -40 to +125 deg C:  http://www.panasonic.com/industrial/batteries-oem/oem/primary-coin-cylindrical/high-operating-temperature.aspx

That web page doesn't say it's lithium, but odds are that it is.  That might be one thing that your client will just have to deal with.  Lithium is no less reliable than other chemistries.  That being said, there are other battery chemistries like Silver Oxide, Zinc Air, and Alkaline Manganese that might work for you-- but a quick search of the Duracell web site didn't return any temperature data for those.

The other option is to do some out of the box thinking.  Maybe a small solar cell plus supercap.