Prove that every permutation matrix satisfies its characteristic polynomial.

I think this is much easier than you are making it out to be. By relabelling, you may assume that the permutation is $$(1,\dots,c_1)(c_1+1,\dots,c_1+c_2)...$$ The permutation matrix of this product of disjoint cycles is a block-diagonal matrix, with the blocks being the permutation matrices of each cycle.

Products and sums of block-diagonal matrices are block-diagonal, obtained by taking the products and sums of each block. Thus a block-diagonal matrix satisfies a polynomial if and only if each block of it does.

Block $i$ certainly satisfies the polynomial $P^{c_i}-I$, your fact 5. Thus this is the zero matrix, and the product of this with anything else is zero, in particular your polynomial is the zero matrix on the $i$th block. Thus your matrix is zero.

This is just an even more elementary version of David Craven's answer.

For each cycle $(i_1, \ldots, i_c)$ of $\sigma$, note that $P^c e_{i_j} = e_{i_j}$, so $P^c - I$ vanishes on $\mathrm{Span}(e_{i_1}, \ldots, e_{i_c})$. Thus $\prod_{i=1}^k (P^{c_i} - I)$ vanishes on this span as well, hence also on the span of these spans, which is the whole space.

The only fact of note we've used is, for every j, $$ \prod_{i=1}^k (P^{c_i} - I) = \left(\prod_{\substack{i=1 \\ i \neq j}}^k (P^{c_i} - I)\right) (P^{c_j} - I), $$ which is of course immediate, e.g. $$(P^a - I)(P^b - I) = P^{a+b} - P^a - P^b + I = (P^b - I)(P^a - I).$$