Caching $_SESSION data for anonymous users
I think your best option is to use 2 cookies. Set one cookie that checks to see if the browser has JavaScript enabled. If JavaScript cookie is not there, the user gets an uncached page. If JavaScript does exist then drop a cookie containing the session data. Do the uncached page check in your settings.php file.

If you have something like Varnish or Nginx on your web stack, checkout ESI as it can work how you want it if the browser doesn't support JavaScript.

Also checkout http://drupal.org/project/authcache as it might be what you're looking for (minus the JS part...)