If you're using memcached already you could store the number in it and update it only when a user logs in/out. If no one is logging in/out, the number isn't changing.
If your site is so popular that hundreds of users are logging in every second you might want to change the logic so that the process to update the count only does so when it has expired from the cache and give it a short expiry time. At that point you probably would want each machine to track its own number to avoid frequent distribution costs. In the end I think you're going to have to get comfortable with the idea that the number will never be exact. If you want exact, you have to pay for it. David