Format of the "string of zeros"?
It's pretty simple to set your Ad Id to a new UUID:
NEWADID=$(cat /proc/sys/kernel/random/uuid)
sed -ri "s/[0-9a-fA-F]{8}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{4}-[0-9a-fA-F]{12}/$NEWADID" </data/data/com.google.android.gms/shared_prefs/adid_settings.xml
At a guess, it will be set to UUID format made of zeros. Might try setting it to that now.