Может ли виртуальная машина работать без публичного IP-адреса?

Да. Необязательно назначать публичный IP-адрес виртуальной машине. Назначение необходимо только для обмена трафиком с интернетом или другими внешними сетями, в том числе для удаленного подключения к виртуальной машине по SSH с вашего компьютера.

Если у вас несколько виртуальных машин и им нужен доступ в интернет, огранизуйте его с помощью SNAT-шлюза. Это позволит сэкономить на аренде публичных IP-адресов, потому что тарифицироваться будет только один публичный IP-адрес для всех машин. При этом доступа из интернета к таким виртуальным машинам не будет.