A runner for AWS Fargate
Amazon recently announced AWS Fargate, a container-running platform where they (AWS) will handle all infrastructure, and all you do is worry about speccing out the containers to be run. Fargate charges per second of usage, and scales indefinitely.
Gitlab Runner should evaluate the use of Fargate as a runner. Fargate differs from docker-machine in the fact that you don't actually spawn machines, but works more like a remote docker server (from what I gather). Gitlab Runner should in this case spawn a fargate "task" as soon as a Gitlab job arrives. There is no need to back off, run one container per machine, or anything like that - just fire away.
Note for gitlab container registry: This would probably work very well with ECR or S3, where bandwith for repository images isn't an issue, as you would potentially be serving up N copies of an image at the same time.