The equivalent result is well known (and made explicit) in the literature on dual Knuth transformations. From there, you can use the fact that $P(\sigma) = Q( \sigma^{-1})$ to complete the proof. I recommend [this paper][1] by Haiman, though I believe it may not be the earliest reference for this. 

Haiman says two skew tableaux are *dual equivalent* if they are **always** of the same shape when acted on by a sequence of jeu de taquin moves. Theorem 2.6 shows this is equivalent to saying they differ by a sequence of elementary dual equivalences, which by Proposition 2.2 act as described in Case 1 or Case 2. Theorem 2.12 shows these elementary dual equivalences can be thought of as dual Knuth transformations. Since 

$$P(\sigma) = Q(\sigma^{-1}) \  \ \text{and} \ \  (k_i\sigma)^{-1} = d_i\sigma^{-1} $$ 

where $k_i$ is a Knuth transformation acting on positions $i-1, i, i+1$ and $d_i$ is a dual-Knuth transformation acting on values $i-1, i, i +1$, we can conclude that $k_i$'s action on $P(\sigma)$ is either Case 1 or Case 2. This can be seen directly by taking the row reading word of $P$ after applying a dual Knuth transformation. The arguments for the aforementioned results are relatively straightforward, and very similar to Marc's post.

I mention this to emphasize that there is **no** analysis of RSK in Haiman's approach. The only fact used is that the row reading word of a tableau inserts the same as the word itself.

Some additional comments:

1) Haiman's work also characterizes the actions possible for the shifted Schensted correspondence.

2) The proofs in Haiman's paper quite nice, especially when confined to the unshifted case. I've been told the goal of the paper was to get around the row-bumping lemmas you are trying to avoid.

3) In the interest of self-promotion, my [paper][2] with Ben Young shows an analogous result for Edelman-Greene insertion (*Commenters: has this been done earlier?*). Work in progress shows the same for Kraskiewicz insertion, a shifted analogue of Edelman-Greene. Our proofs are based on the messy analysis of row-bumping.


  [1]: http://www.sciencedirect.com/science/article/pii/0012365X9290368P
  [2]: http://arxiv.org/abs/1210.7119