How to deal with block cached for anonymous user?
In general the Internal Page Cache is a rather simple solution. If you need more features replace it with Varnish or a CDN. Most of them provide similar features, like for example ESI to serve dynamic blocks if you can't use Javascript. I think most people would use Javascript in this case, though, and there is a fully cacheable solution. You can deliver all eligible node IDs in drupalSettings and then select and fetch a random node in Javascript. Both, the page containing all eligible nodes and the node randomly fetched, are cacheable, so you can provide the dynamic behavior without any performance hit.