First eliminate $x_1$ by solving an ordinary least squares, and then you need to essentially solve a problem of the form: $\min x_2^TMx_2$ s.t. $\|x_2\|=g$, for appropriate $M$. This problem is the famous trust-region subproblem, aka, TRS.
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:
- LSTRS: http://ta.twi.tudelft.nl/wagm/users/rojas/lstrs-paper.pdf
- Moré-Sorensen TRS algorithm (in the book on Trust-region subproblems)
- http://www.optimization-online.org/DB_HTML/2002/09/530.html
Depending on how large $A$ is, or what kind of structure it has, different TRS methods may be preferred. Example, for small matrices, where you can afford to do Cholesky, the More-Sorensen method is usually very hard to beat. If your matrix is however large and sparse, then you might prefer the LSTRS method instead.