Really what should be happening is that Google Play and iTunes should support affiliate tags on URLs/intents that are passed through to the app on install.
Maybe I should have been clearer. I don't mean that it wouldn't be possible, just not a successful business model like it is now.
Maybe it would be less successful, maybe less prevalent, maybe less useful, but I'm pretty sure advertising would still be possible in a world with no device-specific IDs made accessible to the advertisers.