I don't know whether a controller and a router must be accessible on public IP addresses.
Practically - yes. If you only want to run an OpenZiti overlay on totally private address space, you could choose to do that.
The way I put it is, wherever the clients are, they need to be able to address the controller and at least one edge router. So that means in practicality, they should be on the open internet with a public IP.
I also highly recommend you use DNS and not an IP in the off chance the IP of the controller/router change.
I think that's where the commercial openziti services come in.
Many people will want to use tunnels to remotely access their home computers behind NAT without having to set up the public infrastructure.
Since openziti doesn't do NAT traversal, at least one public router is going to be necessary.
That's certainly true. There are some free VPS providers out there (Oracle) that have been used in the past and are pretty generous and have held up to very modest amounts of traffic. There are also some "pretty cheap" providers if free is too weak.
fwiw, the 'commercial openziti' (NetFoundry) provides a productised, supported, very easy to use and deploy at production scale version, whether deploy in cloud, hybrid, or completely airgapped.