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$.