Isn't the IMEI still publicly available?
In Android 6 they even made a special callback result to indicate that the user has refused to give his permission rather than indicating that modem/phone ID wasn't found.
Clearly they are aware of this and do that deliberately.
android.os.Build.getSerial()