Probably you are out of luck because few shared environments are going to let you run your own webserver or let you use any new ports which is necessary since 80 is taken. That said, this will work if your user account has permission. Plack is required for this solution. I rewrote your CGI with CGI.pm. It's more reliable and once you're used to it, much easier to read.
NetWallah's advice is also good, just plack is easier. See also HTTP::Server::Simple::CGI.
Your, sorta, CGI
#!/usr/bin/env perl
# File called pm-1217158.cgi
use strict;
use warnings;
use CGI ":standard"; # Import common functions.
print header(),
start_html("Hello, Nurse!"),
h1("OHAI!"),
end_html();
Run a micro server
cow@moo[323]~>plackup -L Shotgun -MPlack::App::WrapCGI \
-e 'Plack::App::WrapCGI->new( script => q{pm-1217158.cgi} )'
HTTP::Server::PSGI: Accepting connections at http://0:5000/
Then, if you were allowed to start it, you can visit your webhost at port 5000 to see your CGI. Just substitute the "0" in the URL above with the domain or IP.