Can a server with no public IP interface be a NAT?

Surely you can do another NAT in addition to what your provider does.

ufw is just a netfiter script generator. If it isn't able to do its work, throw it away, it only obscures things.

To do NAT, you only need a single rule in the firewall:

iptables -t nat -A POSTROUTING -o eth0 -j MASQUERADE

That's it. This system now will masquerade (NAT) a traffic for any other system, even if traffic subjected to translation comes from eth0. You will need to specify its IP address as a gateway on all other systems.

If you go this route, you also need to manually enable ip forwarding (net.ipv4.ip_forward=1 in /etc/sysctl.conf), disable redirects on all systems (see ..._redirects in /etc/sysctl.conf) and enable rules saving/autoloading (with netfilter-persistent and iptables-persistent packages).

Also, beware of security! If this network also holds machines not under your control, you must filter them in the filter table, FORWARD chain (just permit forward for your machines and disable it for everything else with the policy). Also you can control (filter) access to this NATing machine in the INPUT chain.