Solve $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$ first, it is small enough to handle by dense methods. If there is no solution, there is also none for the original. Otherwise get an (affine) basis of the solution space of $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$; any solution of $A \boldsymbol{x}=\boldsymbol{e_k}$ is in that space. By calculating $A\boldsymbol{y}$ for each basis vector $\boldsymbol{y}$, I think you get another small set of equations for finding the coefficients for writing $\boldsymbol{x}$ in terms of the basis.

Actually you don't need to use $A^T$, you can use $B^T A \boldsymbol{x}=B^T\boldsymbol{e_k}$ for any convenient $B$, such as one of full rank.

This isn't very much thought out; someone will help to streamline it (or tell us it is rubbish).

Solve $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$ first, it is small enough to handle by dense methods. If there is no solution, there is also none for the original. Otherwise get an (affine) basis of the solution space of $A^T A \boldsymbol{x}=A^T\boldsymbol{e_k}$; any solution of $A \boldsymbol{x}=\boldsymbol{e_k}$ is in that space. By calculating $A\boldsymbol{y}$ for each basis vector $\boldsymbol{y}$, I think you get another small set of equations for finding the coefficients for writing $\boldsymbol{x}$ in terms of the basis (maybe this part is wrong; I'm going to bed).

Actually you don't need to use $A^T$, you can use $B^T A \boldsymbol{x}=B^T\boldsymbol{e_k}$ for any convenient $B$, such as one of full rank.

This isn't very much thought out; someone will help to streamline it (or tell us it is rubbish).