Hmm.... whenever I post a problem, the solution seems to magically pop up about 3 seconds after.
If anyone experiences the same problem (headers already sent) - whatever file in the end - the problem is white spaces in the PHP code.
Follow the error by opening the relevant file - look at the row number, and look for white spaces. Use a differend editor then you usually use (I use EditPlus, which is great!).
Delete the white spaces, save and upload the file.
After I did this, the same problem popped up, but now naming a different file. I looked for white spaces in this file as well, deleted them, and now the store is back to normal.
Hope this can help others with the same problem.
FOr the record, I use Magento 126.96.36.199