Did you upgrade to v1.0.1 from the App Store and got locked out of Pokémon GO? Do you use a Pokémon Trainer Club account? I didn't have an older version of Pokémon GO on any of my devices. I did some research and I came across this video that walked me through how to get an older version of an app directly from iTunes. I tested this with my own device, and I can say with confidence that it works! Just follow along with the video and you should be fine. Note, I do not have any Android devices, so I cannot confidently give you advice there.
For Pokémon GO, this is the version number you need: 816780353