I'm using ZF as my axiom system.
Let $X$ be a metric space and $K\subset Y \subset X$. Suppose $K$ is compact relative to $X$.
Let $\{V_a\mid a\in I\}$ be a family of open sets relative to $Y$ such that $K\subset \bigcup V_a$. Then for every $a\in I$, there exists $G_a$, an open subset of $X$, such that $V_a = Y\cap G_a$.
"I want to choose such $G_a$ for every $a\in I$ without the Axiom of Choice."
I have tried to show whether closure of $X\setminus V_a$ is such $G_a$, but it didn't work well so maybe it's not the way of choosing.
Here's what I have proved.
If $A\subset B$ is open (or closed) relative to $B$, then $B\setminus A$ is closed (or open) relative to $B$.
I suppose that you are trying to show that $K$ is compact relative to $Y$ as well.
You don't need to choose $G_a$ and it might be impossible too, instead consider the open cover of $K$ which consists of all such sets, namely:
$$\{U\subseteq X\mid U\text{ is open, and }\exists a\in I: U\cap Y=V_a\}$$
This is an open cover of $K$ in $X$ and therefore has a finite subcover $U_1,\ldots, U_n$. Now show that $V_i=U_i\cap Y$ is a finite subcover of $\{V_a\mid a\in I\}$.
Generally speaking, the whole point in compactness is that it allows us to avoid the axiom of choice by generating finite sets from which we can choose without the axiom of choice. The trick is often "if you can't choose, take anything that fits, and let compactness choose for you".