LU decomposition with pivoting
This is a bipartite matching problem, which has several known algorithms. As a bonus, you get a combinatorial criterion for when it is even possible (namely, Hall's theorem).

Construct a bipartite graph with $n$ vertices on each side $x_i,y_j$. Connect $x_i$ to $y_j$ if $A_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, gives you a permutation $\pi$ such that $A_{i\pi(i)} \neq 0$ for all $i$.