Excessively high temperature reading with LM35
4.15V from Vout to GND with short wires and 5V supply is totally wrong. Either you have the connections wrong or the LM35 is toast. Please double-check the connection vs. the datasheet. 

I suspect just because of that particular voltage reading  that you may have the connections mixed up. 

Edit: Thanks for the photo. Looking at the part from the front (the part with the markings) from left to right, the pin order is: 



Vs, Vout, GND = +5, Vout, GND 

In your photo I see +5, Vout, GND as it should be. So it it's reading more than 10mV/°C at Vout with the blue wire disconnected from the Arduino (and 5V/0V on the orange and black wires respectively) I would say it's dead. Perhaps the power got momentarily reversed on it?