can I use DNS with private NAT addresses?

Can I use NAT to do anything with routing the Domains

No, NAT is not aware of DNS.

Do I need more public ip addresses

You need one IP per server IP:Port tuple. If everything is running on different ports then you could conceivable use the same IP for everything. Just a reminder, IP knows nothing about DNS, and DNS knows nothing about service ports (unless the application specifically supports SRV records, which is crazy rare for reasons unbeknownst to me).

How do other virtualized hosting companies do this? do they have more ip blocks?

Either the application is DNS aware (like HTTP, which uses application layer headers; or TLS, which uses SNI which is like a header) or they use separate IPs per destination.