There are a couple of ways to resolve this.
Grant sudo permissions
You can grant sudo permissions to the gitlab-runner user as this is who is executing the build script.
$ sudo usermod -a -G sudo gitlab-runner
You now have to remove the password restriction for sudo for the gitlab-runner user.
Start the sudo editor with
$ sudo visudo
Now add the following to the bottom of the file
gitlab-runner ALL=(ALL) NOPASSWD: ALL
Do not do this for gitlab runners that can be executed by untrusted users.
SSH Runner
You can configure the gitlab-ci-runner to connect to a remote host using SSH. You configure this to use a user remotely that has sudo permissions, and perform the build using that user. The remote host can be the same machine that the gitlab runner is executing on, or it can be another host.
This build user account will still need to have sudo and passwordless permissions. Follow the instruction below, except replace gitlab-runner with the build user.