There is a (not that) new concept in GitLab: k8s agents.
I am trying to wrap my head around whether the agents are required to run GitLab Kubernetes runners.
Let’s say we have one GitLab instance with multiple projects and X runners registered and running on X k8s clusters (one runner per each k8s cluster). When running a pipeline what is the easiest way to manage where each project’s pipelines should run (on which k8s cluster) ?
I guess one way is to use tags. But that doesn’t work in our case and we need to set the kubernetes context in each job to point it to the correct cluster.
How to work around this (having a lot of jobs in one pipeline) ?
To answer your first question, no, you do not need agents to run your runners in a Kubernetes cluster. You can deploy your runners to your clusters anyway that’s convenient for you, be that kubectl or helm or whatever.
For projects with pipelines that deploy to a cluster you need to set up some way for the deploy job to access the cluster. One way of doing that is by connecting the cluster to the project in the GitLab UI. The old, deprecated way via certificates still works but agents are the way forward.
FYI, I have used both kubectl and helm to bootstrap runners in a Kubernetes clusters and now use a GitLab CI/CD deploy job to keep them up-to-date 
The cluster connection is still certificate based.
Now, for your second question, does it really matter on which cluster each job in any of your pipelines is executed? Is there any problem with job 1 of pipeline a being run on cluster A and jobs 2 and 3 of that pipeline gettting run on cluster B and C?
There is no (should be no) problem running a deploy job on a runner in cluster A that deploys to cluster B (as long as there is a connection between the project and cluster).
I think you should use tags to communicate runner specifics that may matter to jobs, e.g. architecture, the presence of GPUs or SSDs, memory constraints, whatever. Location is hardly ever a concern when it comes to running a job.
In our case it does matter on which cluster a job is executed as on one k8s cluster we have some additional hardware component which is required for some pipelines but the rest doesn’t need it and can be run on any.
I think you’re looking at it from the wrong point of view. Some of your jobs need a specific piece of hardware. Hence, they need runners with access to that specific piece of hardware. Label the runner that have that access in an appropriate way. For example, if those jobs need GPUs, then add a gpu label to the runners that actually provide a GPU. That these runners are all deployed in a certain cluster is just coincidence as far as the job is concerned. That is to say, the job doesn’t care where it is run as long as there is a GPU that it can use. The job might just as well run on a bare metal host. As long as that additional hardware component is available it doesn’t matter. It’s the runners responsibility to communicate its “capabilities”. As long as these match the requirements of the job, the job is good to go on that runner. How the runner is provisioned and what kind of executor it uses is irrelevant.
You say the additional hardware is required for a pipeline but it is only really needed for jobs, not pipelines. Sure, it could be all the jobs in a pipeline, but that doesn’t mean the pipeline needs it. You will need to tag the jobs with special needs to match the runners that meet these needs.
Hope this helps.