Ok the problem was solved by using the manual update described at:

https://docs.gitlab.com/runner/install/linux-manually.html

Stop the service (you need elevated command prompt as before):

sudo gitlab-runner stop

Download the binary to replace Runner's executable:

sudo wget -O /usr/local/bin/gitlab-runner https://gitlab-runner-downloads.s3.amazonaws.com/latest/binaries/gitlab-runner-linux-386
sudo wget -O /usr/local/bin/gitlab-runner https://gitlab-runner-downloads.s3.amazonaws.com/latest/binaries/gitlab-runner-linux-amd64

You can download a binary for every available version as described in Bleeding Edge - download any other tagged release.

Give it permissions to execute:

sudo chmod +x /usr/local/bin/gitlab-runner

Start the service:

sudo gitlab-runner start

"latest" - may install a beta so it is important to select the right tag (also described in the link)

Official answer for this problem (source of the text from the following link):

https://docs.gitlab.com/omnibus/update/package_signatures#update-keys-after-expiry-extension

Update keys after expiry extension

For Debian based distributions:

PackageCloud generally made use of apt-key, which will be deprecated in the future. Manually installed or configured repositories from some distributions are already using the signed-by support within Debian package source lists.

1. Determine if you’re using apt-key or signed-by functionality:

    grep 'deb \[signed-by=' /etc/apt/sources.list.d/gitlab_gitlab-?e.list
   

2. If this grep returns any lines, you're using signed-by functionality. This takes precedence over any apt-key usage. If this grep returns no lines, you're using apt-key functionality.

   For signed-by, the following script (run as root) updates the public keys for GitLab repositories:

   awk '/deb \[signed-by=/{
       pubkey = $2;
       sub(/\[signed-by=/, "", pubkey);
       sub(/\]$/, "", pubkey);
       print pubkey
     }' /etc/apt/sources.list.d/gitlab_gitlab-?e.list | \
   while read line; do
     curl -s "https://packages.gitlab.com/gpg.key" | gpg --dearmor > $line
   done
   

3. For apt-key, the following script (run as root) updates the public keys for GitLab repositories:

   apt-key del 3F01618A51312F3F  
   curl -s "https://packages.gitlab.com/gpg.key" | apt-key add -
   apt-key list 3F01618A51312F3F