I'll keep updating this, in case it should be useful for someone else. I now got it to work. It turns out that Tidal relies on Google Play Services to cast to Chromecast. So when I exclude both Tidal and Google Play Services from Rethink, casting works right away. What this means for my privacy, I don't know - if I'm doing this, every app and connection on my phone is routed through the VPN/custom DNS/bloclist, execpt Tidal and Google Play Services.
I've also been playing around with a Samsung A22 which I'm using without logging in to Google. On that phone, it's enough to exclude only Tidal in Rethink, for casting to work. So it would appear to me that Google Play Services sneaks around the firewall by itself in that case.