Send session tokens in the URL rather than a cookie. Rewrite any URLs on your site to start with the session token (e.g. something like /!3ccc23b0d33fdac693ae2771d72e85f2!/real/page). Have a PerlTransHandler which strips out the token on incomming requests and stashes it with $r->pnotes().

The (excellent) mod_perl Developer's Cookbook (ISBN 0672322404) has a recipie (12.3) for doing just this.