> If I download e.g. uTorrent today and firewall off the hardcoded public bootstrap nodes, will it bootstrap?

Possibly, which mechanisms are used varies from client to client. Usually DHT bootstrap is not a primary goal but a side-effect of other mechanisms. Things that work in some clients:

  magnet -> tracker -> peer -> dht ping
  torrent -> tracker -> peer -> dht ping
  magnet -> contains direct peer -> peer -> dht ping
  torrent or magnet -> multicast discovery -> peer  -> dht ping
  torrent -> contains a list of dht node ip/port pairs

As you can see all but the last piggyback on regular torrent connections. But that's more because file transfers are the primary purpose and the DHT is not the raison d'etre of those implementations. If DHT connectivity were considered more important clients would also try more direct approaches.

> You can ship a client with a long list of "cached" nodes that were verified to be long-lived. I mean you need to obtain the client at some point, you can gather a fresh list of nodes along with it. From that point onward you keep your own cache fresh.

I believe this is how bitcoin works. Or at least it used to.