Too long to comment:
Here is another plausible approach. Consider the convex sets of $\{\lambda, x\}\in R^{2n}$: $$ A\lambda + Bx + C = 0, \lambda \geq 0, $$ and $$ x^2_k\leq \lambda_k, \forall k. $$ The first convex set is a polytope in $R^{2n}$, while each inequality in the second set defines the closed interior of a parabolic cylinder in $R^{2n}$. Note that any point on the boundary of their intersection (convex sets 1 and 2) would be a desired solution. Towards that end, one can possibly use the Alternating Projections method, starting from a point which is not inside any of the parabolic cylinders. Finding such a point can be done this way: (i) choose a random point $\{\lambda^0,x^0\}$, $\lambda^0\geq 0$, (ii) choose a large enough $K>0$ such that $\{\lambda^0,Kx^0\}$ is outside the parabolic cylinders. Intuitively, since iterations of the Alternate Projections would go through points on the boundary of the parabolic cylinders only (projection of an exterior point on a parabolic cylinder will be on its boundary), the limit point should also be on the boundary. Also Also, note that each projection step can be done in polynomial time as the sets are all convex.
Finally, the hope is that the process will converge with a reasonable rate of convergence (this needs further diligence), onto a boundary point of the intersection of the convex sets 1 and 2. Of course, one has to get a bit lucky here.