A short useless answer : try to write $g_3 = P/Q$ with $P$ homogeneous of degree $d+2$ and $Q$ of degree $d$ for $d=1$. If that fails, try again with $d=2$, and so on.
Or you can try to directly guess a good degree so that it will be solvable. Let $R = K[x_1 \ldots x_8]$, denote $R_d$ the subspace of $R$ of homogeneous polynomials of degree $d$, let $R^G$ the subring of $R$ of elements fixed by a subgroup of $S_8$, $R^G_d = R^G \cap R_d$, and $R^G[y]$ be the subring generated by $R^G$ and $y$, and $R^G[y]_d = R^G[y] \cap R_d$.
Let $G$ be the subgroup of order $16$ fixing $g_1$ and $g_2$. Then $R^{S_8}[g_1,g_2] \subset R^G$. For small $d$, the inclusion is strict but Galois theory implies that for some $d$ large enough you will have $R^{S_8}[g_1,g_2]_d = R^G_d$.
The goal is to find two nonzero elements $P \in R^{S_8}[g_1,g_2]_d, Q \in R^{S_8}[g_1,g_2]_{d+2}$ such that $P g_3 = Q$. We know $g_3 \in R^G_2$ thus $P g_3 \in R^G_{d+2}$. The multiplication by $g_3$ map $R^{S_8}[g_1,g_2]_d \to R^G_{d+2}$ is always injective, so its image is a subspace of dimension $\dim_K(R^{S_8}[g_1,g_2]_d)$. If $\dim_K(R^{S_8}[g_1,g_2]_d) + \dim_K(R^{S_8}[g_1,g_2]_{d+2}) > dim_K(R^G_{d+2})$, the intersection of those two is guaranteed to be nonzero, so you will obtain nonzero elements $P,Q$ as wanted.
So first you have to compute all the numbers $\dim_K (R^G_d)$ and $\dim_K (R^{S_8}[g_1,g_2]_d)$, find the smallest integer $d$ such that the inequality holds, then solve an extremely big system of linear equations. Since those dimensions grow like $d^8/8!16$ you should try to pick the smallest $d$ possible. Of course you may not get the smallest polynomials possible, it may happen that there was a linear combination for a smaller degree, but you can't know a priori that it exists.
Finding $\dim_K (R^G_d)$ is a combinatorics problem. It shouldn't be too difficult here, just count the orbits of $R_d$. For $\dim_K (R^{S_8}_d)$ since it is generated by $n$ polynomials, you get it easily with generating functions. For $\dim_K (R^{S_8}[g_1,g_2]_d)$, I'm not certain what the best way is, it doesn't seem too friendly. You don't need to compute it exactly, a good enough lower bound will work too.
You can compute $\dim_K (R^{S_8}[g_1]_d)$. $g_1$ is the root of a degree $105$ polynomial with coefficients in $R^{S_8}$, thus $\dim_K (R^{S_8}[g_1]_d) = \sum_{0 \le i < 105} \dim_K (R^{S_8}_{d-i})$. Next, $g_2$ is a root of a degree $24$ polynomial with coefficients in the fraction field of $R^{S_8}[g_1]$, which gives you a nice enough lower bound for $\dim_K (R^{S_8}[g_1,g_2]_d)$ (you should obtain something equivalent to $d^8/8! 16$)