HTTP::Headers is for http requests, but redirects are for http responses, so I'm not sure if you're trying to make a request or respond to one. If you are responding to one, you can just print each header on a seperate line before the blank line terminating the header:
print "CustomHeader: CustomValue\n";
print "Location: $url\n\n";