Have you tried simply raising the ground of the LM 35 by placing a diode in series with the 0 terminal?

That way you might just add a single 10ct component and get rid of the problem completely.

Just enough to raise the ground of the LM35 above the input sensitivity threshold.

One Si diode would probably work, two Ge in series would be slightly better (because you get more range).

So that would be:

          +
          |
          |
      +---+--+
      | lm35 +---- out
      +---+--+
          |
         ---
         \ /
          v
         ---
          | 
          |
       ---+-- gnd

The diode is 'up side down', you simply use the voltage drop to raise the 0 of the lm35 (like a zener diode), it doesn't know any better and will add the output voltage to the ~0.6 V the diode provides.