Proving that $\neg\forall x\neg G(a,x) \vdash\exists xG(a,x)$ 
How do I prove in natural deduction that 
  $$\neg\forall x\neg G(a,x) \vdash\exists xG(a,x)$$

The only method I can think of is to assume $\neg \exists xG(a,x)$ and prove the formula by contradiction, but it still introduces a negation before the quantifying operator which (I believe) complicates things.
 A: \begin{Grumpy_sermon}
Repeatedly, there are questions here of the form "How do I prove X in natural deduction?"
This is an uncooperative thing to say, but it is worth saying: there is no such thing as "proving X in natural deduction", as if there is a single system to think about.
A natural deduction system of logic is one which allows us to mirror the everyday reasoning practice of making temporary assumptions for the sake of argument and then discharging them (for example, in reductio arguments, or arguments-by-cases, or some quantifier arguments). But that doesn't fix very much.
For a start, there are choices to be made as far as the layout of proofs is concerned -- do we follow Gentzen, or Fitch, or Lemmon, for example? [Historical aside: the latter two, though well known because of the textbooks by the respective authors, are variants of systems earlier proposed by Jaśkowski.]
And having fixed on a layout, what system do we adopt of rules for connectives and quantifiers for proofs of the appropriate kinds? There are lots of combinations available.
In fact, there are almost as many different systems of natural deduction on the market as there are logic textbooks which present a natural deduction system.
So: at least ask: "How do I prove X in a natural deduction system like that in the book by $A$?" (and if it isn't a standard text book, link to lecture notes, or whatever).
\end{Grumpy_sermon)
Having said that, the chances are that in your particular textbook's system you'll need to prove this stated result by assuming the negation of the conclusion and aiming for a reductio, along the following lines (in a Fitch-style layout):
$\quad \neg\forall x\neg G(a,x)\\
\quad \quad \quad |\quad \neg \exists x G(a,x)\\
\quad \quad \quad |\quad \quad \quad | G(a,b)\\
\quad \quad \quad |\quad \quad \quad | \quad \vdots$
Can you see why making that second temporary assumption $G(a,b)$ was the obvious next move? Do you see how to continue?
