Para los que no lo sepan: Android ID es un identificador único para cada dispositivo. Se utiliza para identificar su dispositivo para descargas de mercado, aplicaciones de juegos específicos que necesita identificar su dispositivo (para que sepan que es un dispositivo que se utilizó para pagar por la aplicación) y tal.
Si no tienes un dispositivo rooteado, entonces sería un poco difícil cambiar el ID del dispositivo. Tendrás que formatear completamente los datos de tu dispositivo para cambiar el ID de dispositivo de tu teléfono Android. Como el ID de dispositivo se genera cuando configuras el dispositivo por primera vez, reiniciar el teléfono cambiará el ID de dispositivo Android automáticamente.
Si usted tiene un dispositivo rooteado, a continuación, cambiar el ID del dispositivo es sólo un proceso de dos toques. Puedes usar cualquier aplicación fiable de cambio de ID de dispositivo Android y cambiará el ID del dispositivo por uno aleatorio con sólo dos toques. La aplicación que he utilizado antes es "Cambiador de ID de dispositivos de Silver Lab" pero ya no esta disponible en google play pero puedes encontrarlo buscando en google. el nombre del paquete es: com.silverlab.app.deviceidchanger.free
Espero que le sirva de ayuda.