The Gram Schmidt process works with any inner product. If $A$ is invertible, then $\langle x , y \rangle_* = \langle A x , A y \rangle$ defines a perfectly good inner product.
Remember to use the corresponding norm $\|x\|_* = \|A x\| = \sqrt{\langle x , A^TA y \rangle}$ as well.
So, in the algorithm, replace $\langle x , y \rangle$ by $\langle x , y \rangle_*$ and $\|x\|$ by $\|x\|_*$, and it will produce a set of vectors that are '$\langle \cdot , \cdot \rangle_*$' orthogonal.
And, of course, $\langle x , y \rangle_* = \langle A x , A y \rangle = \langle x , A^TA y \rangle$, so you only need $A^T A$ to do the computations.
Note: I assumed that $A$ was invertible, hence square, which is not what the OP asked. Here is the 'fix' (a minor modification), and some comments:
In all cases, the Gram Schmidt process produces a set of vectors that spans the same space and are orthogonal with respect to the inner product.
If $\ker A = \{0\}$ (ie, A in injective), then $\langle \cdot , \cdot \rangle_*$ is still a valid inner product on $\mathbb{R}^n$. This is true iff $A^TA >0$. The Gram Schmidt process works exactly as you want.
If $\ker A \neq \{0\}$, then a little more care is needed. In this case $\langle \cdot , \cdot \rangle_*$ is a valid inner product on $Q =\mathbb{R}^n/\ker A$, the quotient space, and unchanged will produce a set of vectors (in $Q$) that spans (again in $Q$) the same space as the original vectors. So the Gram Schmidt process will discard vectors that it considers to be zero (ie, vectors for which $\|x\|_*=0$, or equivalently, $x \in \ker A$). So, in this case, the process needs to be modified to retain all vectors, but no longer perform computations on them if they are zero in $Q$. The resulting set of vectors (which includes vectors that would have been discarded by the original process) will still span the original space, and will also be orthogonal in $Q$ (which is what you wanted).