I've supplied with +5V coming from arduino board. I know that the recommened suply is 12V, but it supposed that arduino can manage until 20V.
Well it might manage, but with any extra load from modules powered from the 5V regulator on the Arduino it could push the regulator power consumption over the edge - normally voltage regulators shutdown if they overheat, so you will risk reliability.
I obtain the same 4.6V if a connect the LM35. BTW A0 has 4.6V, A1 has 3.0V and A2,3,4,5... and so on have 0V in "floating connection"
If floating inputs are reading a steady 0, they are either pulled-down to ground or damaged - a CMOS input that's floating _really will float_!
One last possibility - you aren't accidentally causing the analog pins to be OUTPUTs or enabling their internal pull-ups?
You mentioned 19V earlier - that will instantly fry any inputs on a 5V logic chip, so you really really need to be careful wiring things up. Another reason for not running Vin at such a high voltage.