You made the backups at 3 separate locations "Google drive, box cloud storage, android file manager" but I wonder why didn't you consider saving a backup in an offline storage like HDD/USB/Memory card. I have personally reset my phone several times and had to regenerate the 2FA codes every time but never was I worried about my crypto holdings since I always had a backup of it in my HDD.
I know how painful it is to lose the google 2FA and thanks for making this post. I will now regenerate the backup code and save it offline in my HDD.
Yes it was my mistake, thankfully I did save it in my hdd otherwise this wouldn't have happy ending.
@pawanjain is right Im also using my HDD as a backup to all my data like account passwords, google codes, private keys, storing your back up data on online storage is not advisable its too vulnerable if something happens also using paper for backup is not a good idea either like what other user suggests it might get burned or wet easily from natural disasters its very hard to recover unlike HDD.