Hey there, I have rented a bike from this shop:

http://www.intra-radsport.de/default.asp

They had all kinds of bikes when I was there last summer.