I never thought about that - that's a serious problem. I totally understand throwing option #1 and #2 out - they're either impractical or impossible.
I strongly suggest going with option #3. I would really like to avoid seeing another query string parameter - especially one that will be almost guaranteed to be a part of every single request. StackMobile uses option #3 - a sample URL looks like this:
I might also suggest a slight modification to option #3. Can the parameters for the site and the API version be switched around? Then a URL would look like:
Also one question: would the traditional URL paths still be available for non-authenticated requests or would all requests go through api.stackexchange.com
?