Minimizing the 2-norm of $x$ among all least squares solutions is relatively easy to do- this is the pseudoinverse solution. It can be computed using either a rank revealing version of the QR factorization of $A$ (there are specialized versions of this that work well on large and sparse $A$ matrices) or by using the Singular Value Decomposition. Since you're really more interested in minimizing $\| x \|_{1}$, I'll move on to answering that question.
The problem
$\min \| x \|_{1} $
subject to
$\| Ax-b \|_{2} \leq \delta$
is equivalent (with a suitable choice of $\lambda$) to the basis pursuit denoising problem (BPDN)
$\min \| Ax-b \|_{2}^{2} + \lambda \| x \|_{1}$
Minimizing $\| x \|_{1}$ has (in many circumstances) the effect of finding a sparse solution to the problem of approximating $Ax=b$. These sparse approximation problems have been extensively studied because of their application to problems of compressive sensing.
As a practical matter, you probably don't want to limit your $x$ to being an actual least squares solution but rather to set some tolerance on $\| Ax-b \|_{2}$. If for some reason you do need to have an $x$ that is actually a least squares solution, you can start by finding any least squares solution $\hat{x}$, then let $\delta=\| A \hat{x} - b\|_{2}$.
Algorithms for solving these sparse norm approximation problems are specialized enough that you're probably best off making use of existing software rather than trying to implement the algorithms yourself. I would recommend the list of software packages (as well as the many references to books and papers) at
http://dsp.rice.edu/cs