From CGI.pm docs:

  print redirect(-uri=>"http://somewhere.else/in/movie/land",
                                  -nph=>1,
                                  -status=>301);
[download]

  The -status parameter will set the status of the redirect.  HTTP
       defines three different possible redirection status codes:

            301 Moved Permanently
            302 Found
            303 See Other
 The default if not specified is 302, which means "moved temporarily."
       You may change the status to another status code if you wish.  Be
       advised that changing the status to anything other than 301, 302 or
       303 will probably break redirection.

That means, I cannot return 404, if I redirect. Is there any way around?