The unique phone ID (IMEI), and less importantly, Android ID and carrier information can be obtained by apps without any permission requests. Like internet access, it’s provided by default. As the article mentions, some of it can be mitigated in 6.0+, but ideally, you should be spoofing your IDs using XPrivacy or similar.
“The downside of using a device-level ID is, well, whoever has that data knows a lot about what you’re running. That lets them tailor adverts to your tastes, but there are certainly circumstances where that could be embarrassing or even compromising. Using the IMEI for this is even worse, since it’s also used for fundamental telephony functions – for instance, when a phone is reported stolen, its IMEI is added to a blacklist and networks will refuse to allow it to join. A sufficiently malicious person could potentially report your phone stolen and get it blocked by providing your IMEI. And phone networks are obviously able to track devices using them, so someone with enough access could figure out who you are from your app usage and then track you via your IMEI.”