For some reason, ColdFusion had this limitation back (can't both set cookies and do a redirect). I have no idea if it's been fixed in ColdFusion, as I haven't used it for years, but you can with mod_perl.

I think you can do it if you just generate the headers yourself, rather than have the CGI module do it for you.