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
No. In fact two permutations are equivalent in that sense, (ie conjugate), if and only if they have the same "signature", meaning that the decompositions into disjoint cycles have the same number of cycles of a given length.
So for example in $S_8$ the permutations $P_1=(1,2)(3,4)(5,6,7,8)$ and $P_2=(1,2,3,4)(5,6,7,8)$ are not conjugate, even though they're both even and have "trace" zero (no fixed points). Anything conjugate to $P_2$ must be the product of two disjoint cycles of length four, hence cannot be $P_1$.
Now say $P_1=(a,b)(c,d,e)$ and $P_2=(s,t)(u,v,w)$ are two disjoint-cycle decompositions. Then $P_1$ and $P_2$ are conjugate. $P_{12}$ will be a permutations that maps $a$ to $s$, $b$ to $t$, etc., and maps the fixed points of $P_1$ to the fixed points of $P_2$.