cgi End of script output before headers

Wrong interpreter:

First of all, you should check if the script is error free by running it separately. This you have done already so we are good here. As it happened in my case, when I tried this, it gave me back /usr/bin/python: bad interpreter: No such file or directory error. Problem was that I had used an old script that was using an interpreter as #!/usr/bin/python instead of #!/usr/bin/python3.

Permissions and users:

Secondly, It can be a permissions issue. See this answer

Encoding issues:

At times it can be an issue with encoding if you have a script that has windows encoding. Try dos2unix to remove any encoding issues