How to find least square solution to Ax=b when columns of A are not linear independent? Let $A =\begin{bmatrix} 0 & -1 & 0 \\ 1 & 2 & 1 \\ 1 & 1 & 1 \\\end{bmatrix}$ and $b =\begin{bmatrix} 1 \\2\\ 3 \\\end{bmatrix}$
I couldn't just solve $A^TAx=A^Tb$,  since the columns of A are not independent, I was told by my professor that I must find another matrix with same $im(A)$ 
I found the image of A = $\text{span}\left\lbrace\begin{bmatrix} 1 \\0\\ 1 \\\end{bmatrix},\begin{bmatrix} 0 \\1\\ 1 \\\end{bmatrix}\right\rbrace$
How do we go from here to find another matrix and find the least square solution to the equation?

I don’t understand either what you are having issues with, or what your professor told you to do.
The first thing to notice here is that the system has solutions! So a “least squares solution” really just means a regular solution. If you solve the system directly, you get $x=4-t$, $y=-1$, $z=t$. So those are “least squares solutions”.
The second thing to remember is that even if it didn’t have solutions, there is still no problem. If $A^TA\mathbf{x} = A^T\mathbf{b}$ has multiple solutions, then they all give you least squares solutions: they all end up in the same point when you apply $A$, and that point will be the one closest to $\mathbf{b}$ in the range of $A$. There is absolutely nothing else to be done.
Even if you don’t notice that the system actually has exact solutions, you can just proceed as usual.
You want to find a least squares solutions; you solve the system $A^TA\mathbf{x} = A^T\mathbf{b}$. Now, if $A^TA$ is invertible, then this system has a unique solution. When $A^TA$ is not invertible, then the system will have multiple solutions, and any such solution will be a least squares solution.
Here, we have
$$\begin{align*}
A^TA &= \left(\begin{array}{rrr}
0 & 1 & 1\\
-1 & 2 & 1\\
0 & 1 & 1
\end{array}\right) \left(\begin{array}{rrr}
0 & -1 & 0\\
1 & 2 & 1\\
1 & 1 & 1
\end{array}\right)= \left(\begin{array}{ccc}
2 & 3 & 2\\
3 & 6 & 3\\
2 & 3 & 2
\end{array}\right)\\
A^T\mathbf{b} &= \left(\begin{array}{rrr}
0 & 1 & 1\\
-1 & 2 & 1\\
0 & 1 & 1
\end{array}\right) \left(\begin{array}{c}1\\2\\3\end{array}\right) = \left(\begin{array}{c}5\\6\\5\end{array}\right).
\end{align*}$$
This system has solutions. Using Gaussian elimination, we have:
$$\begin{align*}
\left(\begin{array}{ccc|c}
2 & 3 & 2 & 5\\
3 & 6 & 3 & 6\\
2 & 3 & 2 & 5
\end{array}\right) &\to \left(\begin{array}{ccc|c}
2 & 3 & 2 & 5\\
3 & 6 & 3 & 6\\
0 & 0 & 0 & 0
\end{array}\right) \to \left(\begin{array}{ccc|c}
1 & 2 & 1 & 2\\
2 & 3 & 2 & 5\\
0 &0 & 0 & 0
\end{array}\right)\\
&\to \left(\begin{array}{rrr|r}
1 & 2 & 1 & 2\\
0 & -1 & 0 & 1\\
0 & 0 & 0 & 0
\end{array}\right) \to \left(\begin{array}{ccc|r}
1 & 0 & 1 & 4\\
0 & 1 & 0 & -1\\
0 & 0 & 0 & 0
\end{array}\right).
\end{align*}
$$
So the solutions are given by $y=-1$, $z=t$, and $x=4-t$. These are exact solution, but even if they were not, any such solution would have the same image under $A$ and that image would minimize the error, i.e., be a least squares solution.
