It is unlikely that you can solve such a system exactly. An $n \times m$ system with $n < m$ means that you have fewer equations than you have unknowns. There are two possibilities: either the columns of $A$ are not all linearly independent, and the resulting rank of $A$ equals the row dimension, in which case you just delete the dependent columns; or you must use some sort of optimization routine to minimize a squared-error. See, for example, my response here: https://math.stackexchange.com/a/173259/31475
Edit: I overlooked your comment regarding rank.
Since $\rm{rank}(A) = n-1$, then you definitely have more "unknowns" in $x$ than you have equations. The rationality of entries of $A$ likely has no effect; only in the instance that you expect $x \in \Bbb Q^m$ would you be able to possibly exactly solve such a system (and even then, not guaranteed).
In any case, running time for Gauss-Jordan is, if my memory serves, $\mathcal{O}\left(n^3\right)$.