My perspective, coming to perlish ways from an html background, is that using a meta refresh (or, recognizing that some search engines penalize those, using an intermediate page) is an absolutely standard technique, involving minimal muss and fuss.

Granted that those "If you are not redirected within 5 seconds...." pages can be annoying, a little agita seems bearable if that statement you quote, "effectively means you cannot Redirect and send a cookie on the same request," is fundamentally accurate.

All that said, I suspect there is a perlish way to do what you're seeking... but I also suspect that that mechanism, if one exists, will be kludgy, hackish, or (worse) utterly unsafe.