And then, I'd analogwrite 5v to output pin D9 and 1v to D10 (thus giving an difference in potential of 5-1=4v) so that when LM35 outputs a negative value (let's say, -1v) I would read it in A0 as 0v. Does that make sense or I'm way off course?
Way off course I'm afraid, analogWrite () doesn't output analog values. It generates pulse-width modulation, despite the name.
Since the device takes less than 60uA current you could, at a pinch, provide the 1V rail for the gnd terminal of the LM35 from a resistor divider - use 1k and 3k9, so you'll get about 1V at the gnd terminal - you then measure that as well as the output voltage using two analog inputs and take the difference. Don't forget the load resistor on the output in this mode (which should be about 20k).