Thought I’d write this up for googlability and my own future reference:
Other than the reasons outlined in the Apache FAQ, the error log message “Premature end of script headers” for a CGI script (in my case a Ruby script on Dreamhost) can also mean that the directory containing the script is world-writable.
So folder permissions like
drwxr-xrwx can cause this error.
chmod 755 mydir would change those permissions to
drwxr-xr-x and all is well.
I suppose Apache/suEXEC takes issue with running stuff that any evil user can edit.