Okay, I have some updates. I followed your steps @freibadschwimmer, were able to write the gps.conf and edited the things @lklaus told me. Still not working (I think one time SatStat was able to get my location, but with an error of 13 km …). So I did a hard reset. Then I downloaded FasterGPS from F-Droid, which can write the gps.conf file just by telling it in which region you are. My gps.conf file now looks like that:
Still it is not working… Maybe it really is a hardware problem in my case?