Your problem seems to be solvable as a so-called *trust-region subproblem*, aka, TRS, (the constraint $\|x_2\|=g$ may be written with an appropriate diagonal matrix as $\|Dx\| = g$).

Please have a look at the following references (and references therein), which provide algorithms and discussion on how to solve such problems; perhaps you can simplify or adapt one of their methods:

1. LSTRS: http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf
2. Moré-Sorensen TRS algorithm (in the book on Trust-region subproblems)
3. http://www.optimization-online.org/DB_HTML/2002/09/530.html

It seems that the Newton method suggested by Robin above might work for you. The TRS methods organize their computation for speed, so in case your matrix $A$ is large, a more careful implementation might help.