What is the fastest algorithm to compute rank of a rectangular matrix?
You can bring a $2n \times n$-matrix into echelon form in time 
$O(n^{\omega + \epsilon})$ for any $\epsilon &gt; 0$. See the book "Algebraic Complexity Theory" by Bürgisser, Clausen, Shokrollahi, Section 16.5.

Now you apply this procedure $m/n$ times to your $m \times n$-matrix.
This gives an algorithm with $O(mn^{\omega-1})$ arithmetic operations.

If you bring an $2n \times n$-matrix into echelon form, then it contains
a zero matrix of size $n \times n$ afterwards. You take the remaining $n \times n$-matrix,
add a new $n \times n$-block of your input matrix and bring this to echelon form and so on.