Now who's going to provide an equally nice proof for U-perm plus A-perm?
There may very well be a simpler proof, but here's one I've come up with.
Proof that all Rubik's cube positions with an even permutation of the corner cubies can be solved using only A-perms, U-perms, and cube rotations.
First, define A-perm as:
A = R B' R F2 R' B R F2 R2
Next, define U-perm as:
P = R2 U' F B' R2 F' B U' R2
Now, it is taken here that it is a well-known fact that all Rubik's cube positions having an even permutation of the corner cubies also have an even permutation of the edge cubies, and can only be solved using an even number of quarter-turns. If a position can be solved using an even number of quarter-turns, we can partition the solution into a sequence of pairs of quarter-turns. Therefore, to complete the proof, we just need to prove that all pairs of quarter-turns can be performed as a combination of A-perms, U-perms, and cube rotations.
For any pair of quarter-turns, a cube rotation can be performed to make the first face to be turned the U face. If the 2nd quarter-turn of the pair is an adjacent face, the cube can be rotated so that the 2nd face to be turned will become the R face. Thus, we only need to prove the condition for the following pairs of quarter-turns:
U2, U R, U R', U' R, U' R', U D, U D', U' D, U' D'.
First, the move U2 can be expressed in terms of the above A-perm and U-perm along with cube rotations as:
U2 = A P y A P y'
Let's assume U R also satisfies the condition. Then, we know that the remaining pairs in the list satisfy the condition by the following algs in terms of U2, (U R), and cube rotations:
U R' = (U R) z' U2 z
U' R = U2 (U R)
U' R' = (U2) (U R) z' U2 z
U D = (U R) z' U2 (U R) z
U D' = (U R) z' U2 (U R) z' U2 z2
U' D = U2 (U R) z' U2 (U R) z
U' D' = U2 (U R) z' U2 (U R) z' U2 z2
Now, all that is left is to prove that (U R) can be performed in terms of A-perms, U-perms and cube rotations.
Before doing that, the following alg for twisting two adjacent corners will be defined. Note that U2 was expressed above in terms of A-perm, U-Perm, and cube rotations; so it is assumed that U2 in the alg below represents the equivalent sequence instead of simply a single U2 turn. (Actually, for this particular alg, the U2 can be replaced simply with (A y A y') since we don't need to move the edge cubies with respect to the centers.)
T = A x' U2 x' U2 x' y A y' x U2 x U2 x
Finally, a formula is provided for (U R) in terms of the above A-perm and U-perm as well as cube rotations (and also the above corner-twisting alg which was defined in terms of the same maneuvers). (Note, A2 means the A-perm alg executed twice, and P2 means the U-perm alg executed twice.)
U R = z' y2 P z' y' P2 y z P2 z' y A2 P2 x' P2 y A2 y2 T z' y2
Hence, all possible pairs of quarter-turns can be performed, so it is possible to solve all Rubik's cube positions with an even permutation of the corner cubies using only cube rotations and the specified A-perm and U-perm.
I have not even started thinking about the corners though. I think this would be possible to do if you scramble with only U and A perms, but I am not sure otherwise, because many times you will need to do an AUF, and you can't do that. 
