There really should be a capacitor across the input and ground when there is much length between the regulator IC and the power supply caps; without that, the regulator might go into oscillations and the output could actually measure higher than the input.

 

@all
Thank you for your suggestions. I finally got the LM317 to work today. My connections were correct all the time.

Unfortunately all the 3 LM317's that I used yesterday died. The most probable suspect is the power supply which is pretty low quality. I tested today with a 12V battery and another 12V power supply and it is working great. I found today that the breadboard had melted at the rows where I had the 317 connected, so it seems there was a surge which fried the 317.
Another suspect is the 100uF capacitor at the output that I had used for some time yesterday. As per the datasheet, it is recommended to use protection diodes if the cap value is greater than 25V. Since I did not use the diodes, it might have damaged the 317. But it does not seem that the surges from 100uF cap would melt the breadboard plastic.