Смог запустить Парсер на nginx. Поставил FastCGI-сервер SimpleCGI, он принимает на вход FastCGI-запрос и запускает по нему CGI-программу. Написан на Перле, который я хорошо знаю, поэтому мне сразу видно как его можно настроить. Настройки nginx получились следующие:

server {
        listen 80;

        server_name  parser.internal;
        set $root /var/www/parser;
        root $root;

        location ~ \.(p|cgi)$ {
            include fastcgi_params;
            fastcgi_pass unix:/var/www/cgiwrap-dispatch.sock;
            fastcgi_param  SCRIPT_NAME  $fastcgi_script_name;
            fastcgi_param  PATH_INFO    $fastcgi_script_name;
            fastcgi_param  PATH_TRANSLATED $root$fastcgi_script_name;
            fastcgi_param  SCRIPT_FILENAME  $root$fastcgi_script_name;
        }
}

SimpleCGI после запуска создаёт файловый сокет «cgiwrap-dispatch.sock» к которому и обращается nginx.

Причём, что интересно, с SimpleCGI спокойно работает и Парсер из пакета, на который я жаловался, что он падает из-под thttpd.

Добавлено позже: если нужно указать путь до auto.p, то можно добавить «fastcgi_param CGI_PARSER_CONFIG путь/до/auto.p».