I'm sure you're getting a 404 error because there's either something wrong with your header or your URL is wrong (most likely the latter, IMO). Your redirect header also needs to be the first thing printed from your script.
To answer your other questions: If you're using perl, you can use CGI in most cases. The CGI perl module is part of all modern perl distributions. And in terms of using "parts" of CGI- yes, you can. Another lovely thing about perl is that it doesn't force you into one way of doing things. Why don't you try the code that Projekt21 suggested and see what shakes out?
-Any sufficiently advanced technology is
indistinguishable from doubletalk.