Bienvenido a los foros de Perl en Español, almez.
El error 500 sí que suele ser un fallo de los permisos de ejecución, pero como dices, le has dado permisos al fichero. ¿Tiene la carpeta cgi-bin/ permisos 755 para que el servidor web también pueda entrar y leer el programa? ¿Seguro que la extensión permitida es .pl? ¿no será .cgi? Esto último lo debe indicar el administrador del sistema.
Lo ideal es que tengas acceso a los registros (log) de actividad del servidor web. En el error.log aparecerá el porqué ha ocurrido el fallo.
Cuando puedas, haz una prueba con mi
CGI mínimo, que, con la ayuda del módulo CGI::Carp sacará los posibles errores en pantalla, y quizás te dé más pistas. Si no da ninguna, entonces sí que hay un problema porque el servidor no ha podido ni siquiera ejecutarlo.
Del ejemplo que has puesto, yo quitaría el exit(1); y el espacio en blanco que hay después de la palabra 'html', pero juraría que está todo bien.