Ok, I think I may have a proof that is satisfactory for my purposes.
Proof by induction. If a permutation $\sigma$ of a matrix $\mathbf{A}$ comprised of $n$ individual row and column permutations can be written in the form $C_{post}RC_{pre}$ (where $C$ is a sequence of permutations applied to individual columns of the matrix and $R$ is a sequence of permutations applied to individual rows of the matrix), then a sequence of $n+1$ individual row/column permutations formed by applying an additional permutation after $\sigma$ can also be written in the form $C_{post}RC_{pre}$.
Base case: the identity permutation $\sigma_I(\mathbf{A}) = \mathbf{A}$ is of the form $C_{post}RC_{pre}$ where $C_{post}$, $C_{pre}$ and $R$ are all empty sequences.
Consider now the permutation $\sigma$ which is comprised of $n$ row and column permutations:
$$\sigma(\mathbf{A}) = (C_{post}R_0C_{pre})(\mathbf{A})$$
Now consider adding a single permutation (either a row permutation $\sigma_{R_i}$ or a column permutation $\sigma_{C_j}$). There are two cases:
$$\sigma^{\prime}(\mathbf{A}) = (\sigma_{R_i}\sigma)(\mathbf{A})$$
$$\sigma^{\prime\prime}(\mathbf{A}) = (\sigma_{C_j}\sigma)(\mathbf{A})$$
In the case of $\sigma^{\prime\prime}$, an additional column permutation is applied, which does not change the form of $\sigma$, so $\sigma^{\prime\prime}$ can be written as $C^{\prime}_{post}R_0C_{pre}$.
In the case of $\sigma^{\prime}$, we notice that the last three terms are in the form $R_{post}CR_{pre}$:
$$\sigma^{\prime} = \sigma_{R_i}C_{post}R_0$$
A sequence of row permutations followed by a sequence of column permutations, followed by a sequence of row permutations can also be written as a sequence of column permutations followed by a sequence of row permutations followed by a sequence of column permutations. That is,
$$\exists R^{\prime}, C^{\prime}_{pre}, C^{\prime}_{post} : R_{post}CR_{pre} = C^{\prime}_{post}R^{\prime}C^{\prime}_{pre}$$
Therefore, we can rewrite $\sigma^{\prime}$:
$$\sigma^{\prime} = C^{\prime}_{post}R^{\prime}C^{\prime}_{pre}C_{pre}$$
Therefore, a sequence of $n + 1$ individual row/column permutations formed by applying an additional permutation after a sequence of $n$ row/column permutations which is in the form $C_{post}RC_{pre}$ can also be written in the form $C_{post}RC_{pre}$. Since this is true for the base case ($n = 0$), and is true for $n + 1$ if $n$ is true, then it is true generally for any number of individual row/column permutations.
Best Answer
Here's a proof that a regular bipartite graph has a perfect matching: Show that a finite regular bipartite graph has a perfect matching.
Your matrix corresponds to an $m$-regular bipartite graph in which the rows and the columns form the two vertex classes and the ones determine the edges. A perfect matching is a matching in which every vertex is incident to exactly one edge of the matching. This corresponds to a permutation matrix, and subtracting out this matrix leaves $m-1$ ones in each row and column.