Can a nonsingular matrix be column-permuted so that the diagonal blocks are nonsingular?

Yes, it's always possible. For any positive integer $k$, define $[k]={1,2,ldots,k}$. Let $I=[n]$. By Laplace expansion theorem, $$ det(A)=(-1)^{sum_{iin I}i}sum_{Jinbinom{[n+m]}{m}}(-1)^{sum_{jin J}j}det(A[I,J])det(A(I,J)),tag{1} $$ where:

• $binom{[n+m]}{m}$ is the set of all strictly increasing sequences of $m$ distinct indices chosen from $[n+m]={1,2,ldots,n+m}$,
• $A(I,J)$ denotes the submatrix of $A$ obtained by removing all rows indexed by $I$ and all columns indexed by $J$, and
• $A[I,J]$ denotes the submatrix of $A$ obtained from the rows indexed by $I$ and the columns indexed by $J$, i.e. it is the submatrix complementary to $A(I,J)$. Formally, $A[I,J]=A([n+m]-I,,[n+m]-J)$.

It follows from $(1)$ that if $A$ is nonsingular, $det(A[I,J])det(A(I,J))$ must be nonzero for some $J$. Hence $A[I,J]$ and $A(I,J)$ are nonsingular. Let $P$ be any permutation matrix whose first $n$ columns are the standard basis vectors $e_j$s such that $jin J$. Then the result follows.