Your worries about compatibility can be solved using different solutions to the same problem. If you don't want cookies, then just use something like Apache::SessionManager, which can handle sessions inside URIs.
Of course, this doesn't resolve privacy issues, as you can imagine, because it is still possible to track a user even without cookies. On the other hand, it would be quite impossible to put something in a basket on Amazon or build something like PMonks, without something holding a state. So there is no escape, except honesty.
BTW, it is possible to expire AuthBasic accounts. Using cookies, just send an empty cookie (delete it) and the user will not enter your site without re-authentication. Under AuthBasic, just disable an account inside your htpasswd file. But you will need some more glue :-))