Is it possible to build a site without Users and Node? It's hard for me to imagine any site that could be built without the Users and Node modules.  Having them as modules makes it possible to replace them with alternatives, I suppose, but they are so fundamental to how Drupal works that I would suspect that anyone who wants different behavior would probably just skip Drupal altogether, since replacing these might break most of the other modules you might use.

Is it possible to build a Drupal site without Node and Users?  Has it actually been done, or is it just a theoretical possibility?
With Drupal 7 and a reasonable amount of effort, I don't actually believe it's possible.

Drupal 8 however will further decouple the modules, so that you can (hopefully) truly build a site without it.

A good use case for disabling User, is as a security hardening mechanism. Have your production site completely disallow logging in by not having the module, and push content from an internal stage environment instead with the help of something like Deploy.

A good use case for disabling Node could be a file handling API. One would need the file entity, but then only communicate with the world through a REST based API. No nodes (or even theme) needed.