1) I assume that on Linux your scripts have unix style line endings, i.e. linefeed as opposed to windows carriage return linefeed. A bang line of "#!/usr/bin/perl^M" would try to run perl^M which wouldn't exist. Below is one way to check. Note the \r after p e r l

od -c delme.perl | head
0000000   #   !   /   u   s   r   /   b   i   n   /   p   e   r   l  \
+r
0000020  \n   ..... etc ...
[download]

Though if the bang line was the problem I'd think you would get a 500 server error, rather than have the file served up to you.

2) chmod 700 will work only if the owner of the script is the same as the effective user that apache runs as. You could try chmod 755 instead.

As others have suggested the problem may lie in your apache configuration. Perhaps your cgi-bin is screwy. I don't think apache on linux needs to know that ".pl" files are associated with /usr/bin/perl, nor does the ".pl" file name extension need to be associated with cgi programs as long as the files are under your cgi-bin directory and not under your docs directory. It's been a while since I worked with apache, so I could be mistaken.