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:

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

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.