Two thoughts (just off the top of my head):

• Set the cookie (which sends a header, IIRC), then print a blank page with a meta refresh tag, using the redirect url and a short (1 second may be the smallest increment) refresh time.

or..
• Set the cookie, then use something like LWP::Simple to get the contents of the redirected page and print that. One caveat though, if the redirected site isn't your own, they may not appreciate this (though I assume if you're redirecting to another site, you're probably the owner of the other site as well).

Just a thought on the matter, good luck! :)