It might be wise to see how other vendors are currently handling this problem.
For example, if you take a look at Amazon's IoT button's technical specs you'll see two things that directly relate to your question.
First, they use device serial numbers in the form of
"serialNumber": "GXXXXXXXXXXXXXXXXX"
Where each X is a mixture of letters and numbers and the G listed above is simply the letter G which happens to be the first character of the serial numbers for this product. This is quite a large amount of address space for numbering devices and the numbers themselves are fairly straightforward. Assuming they don't use the letters "o" due to confusion with the number zero (the letters are all capitalized so I and L might be in use) this is roughly 35^17 unique serial numbers give or take a few numbers they may or may not use it's an insanely huge number, more than 25 digits long. For most vendors this serial number, or it's equivalent, is programmed into the hardware and it is probably very easy to do when they are created.
Then, in the case of Amazon IoT, they have a system to allow customers to create their own PKI X.509 certificates or simply download unique PKI X.509 certificates created by Amazon on demand to their devices.
If you look more closely at the size of X.509 keys and their relative keyspace (which could also be effectively expanded by using certificate options) you'll see that size of keyspace for Billions of devices is not a problem at all.
The bigger problem is getting unique certificates onto the devices and managing them. This can be a lot of work if not done at a factory.
Per the device changing networks, I have to connect the device to each 802.11 wireless network I use manually. Then it uses MQTT to call home
Per the device changing ownership, in the case of Amazon's IoT you could simply transfer the device with it's existing serial number to a new owner and have them generate new certificates.
There are several other commercial IoT ecosystems which do things in their own way but generally, and as far as your question is concerned, this is how it works and size isn't really a problem for the scale you mentioned.
Important Note: Not all vendors allow customers to use their own PKI and this can create another problem where there are multiple copies of public-private key pairs. Likewise, some vendors simply aren't concerning themselves with security at all at this time.
Useful references:
http://docs.aws.amazon.com/iot/latest/developerguide/iot-gs.html
https://aws.amazon.com/iotbutton/faq/
https://en.wikipedia.org/wiki/X.509
https://www.ietf.org/rfc/rfc5280.txt