perl scripts go in /Library/WebServer/CGI-Executables
call them like this: http:/127.0.0.1/cgi-bin/myScript.pl
you said you've correctly changed the permissions, but, if you get a 500 error, chances are that the line breaks are Mac instead of Unix. you can fix this easily in Terminal, as follows:
type perl -pi -e 's/\r/\n/g' (leave a space at the end), and then drag your file(s) onto the Terminal window and hit Enter. try the file in your browser again, and it should work fine.
hope that helps