Find my iPhone without full internet access
There are solutions for this.  A good number of our clients use a Junos VPN portal for telecommuting associates.  Meanwhile, Junos provides a free iOS VPN client that integrates very nicely with the on-device OS.  Though I'm not aware of other VPN products (it's not my side of the business) I'm reasonably certain there are other products with similar functionality.

My solution would be to set up the VPN, then allow a specific rule to go back out to the iCloud service.  If you're dead-set on using iCloud to monitor location, that's probably your best option.  Apple Configurator does not currently allow for supervising a device's location, but I wouldn't be surprised if they added it for supervised devices in the future.

Another alternative would be to check out the available documentation from Apple to see if there's a specific feature for your use-case.