The "lab" environments have enough capacity to allow plenty of parallel testing. When deploying to production, it's expected that you already know your branch does what it's supposed to do. A production deploy is when one makes sure a branch has not introduced regressions, so holding it for more than 15 minutes is rare.

I imagine deploying a green environment[0] to test before merging to master would be one solution. It is interesting that Github seem to not do that.

0: http://martinfowler.com/bliki/BlueGreenDeployment.html

I suppose you could have a hierarchy, with team leads pulling from their devs and deploying the whole team's stuff when it's ready.