Using a private Docker Image from Gitlab Registry as the base image for CI

All of the above answers including the acepted one are deprecated, This is possible in 2021:

https://docs.gitlab.com/ee/ci/docker/using_docker_images.html#access-an-image-from-a-private-container-registry

---

TL;DR

Set the CI/CD variable DOCKER_AUTH_CONFIG value with appropriate authentication information in following format:

Step 1:

# The use of "-n" - prevents encoding a newline in the password.
echo -n "my_username:my_password" | base64

# Example output to copy
bXlfdXNlcm5hbWU6bXlfcGFzc3dvcmQ=

Step 2 (This JSON is the value to be set for DOCKER_AUTH_CONFIG variable):

{
    "auths": {
        "registry.example.com:5000": {
            "auth": "(Base64 content from above)"
        }
    }
}

Now it's possible, they have included that option months ago.

Use gitlab-ci-tokenas user and the variable $CI_BUILD_TOKEN as password.

This example works on GitLab 8.13.6. It builds the test image if needed, and in the next stage uses it to perform syntax checks:

build_test:
  stage: build_test_image
  script:
    - docker login -u gitlab-ci-token -p $CI_BUILD_TOKEN $CI_REGISTRY
    - docker build -t $CI_REGISTRY_IMAGE:test -f dockerfiles/test/Dockerfile .
    - docker push $CI_REGISTRY_IMAGE:test
  tags:
    - docker_build
  environment: test

test_syntax:
  image: $CI_REGISTRY_IMAGE:test
  stage: test
  script:
    - flake8 --ignore=E501,E265,E402 .

UPDATE: Re-reading the question, the accepted answer is correct. In my example, the job test_syntax will fail to authenticate to the registry, unless the user logins manually from the runner machine. Although, it can work if the 2 runners are on the same host, but it's not the best solution anyway.

In gitlab-ci-multi-runner 1.8 there's an option to add the Registry credentials as a variable, so you only need to login once to get the encoded credentials. See documentation.