Do they have to give different IPv4 addresses?
This is very possible. This type of NAT is called Carrier grade NAT (CG-NAT) and is supported by most vendor (Juniper, Cisco Alcatel) equipment.
If the carrier uses NAT, the carrier can reuse addresses in different locations. This is how home networks can all reuse the same subnet and addresses.
NAT masks the assigned address behind a globally unique address.