I assume througout that there is no problem with mining and I ignore the subtleties of difficulty changes throughout.Ex: I go to blockchain.info and see that the last block was created 60min ago. I think "oh, how unlucky the miners have been, but that's good, then they should find a new block any second now."
Is that correct, or should I expect the average time until a new block is 10min no matter how long ago the last block was created?
No, this is not correct. If you see that the last block was created 60 mins ago then the expected waiting time until the next block is 10 minutes and the expected length of time between the current block and the next block is 70 mins.
If blocks are solved every 10 minutes on average, then shouldn't the average answer to the question "How long do I need to wait until the next block is solved?" be 5 minutes?
Good question. You've stumbled into a probability paradox.
Consider also that the block-generating process looks exactly the same with time reversed. If you select points in time uniformly (between 2010-01-01 and 2012-12-31 say) you'll find that the next block is, on average, 10 minutes into the future just as you find that the previous block is, on average, 10 minutes into the past. You'll find that the average time interval between the previous and next blocks is indeed 20 minutes!
In this case the marks aren't evenly spaced, but I have trouble seeing why that matters over a long timespan since the intervals average out to once per 10 minutes.
Resolving the paradox:
Selecting a block at random is different to selecting a point in time at random. When selecting a point in time at random you're more likely to land between blocks which are far apart than blocks which are close together. Your averages are then biased towards longer waiting times.