In-store iPhone 5 battery replacement?
I had a battery replaced on the day after iPhone 6 launch and the process took 50 minutes door to door. (Entering the store to leaving). We did have a reservation and chose to stay past the "50 minutes" to let the iCloud restore finish and get key apps from the in store cache / fast internet. 

I would expect you might get in and out 10 minutes quicker on a less busy day and could wait twice that if several phones were ahead of you to have batteries replaced.