For the rolling shutter issue, you can check AE CS6 built in tool,
Effect > Distort > Rolling Shutter Repair, if you haven't already. This basic tool is useful in some of the shuts but in more action packed footage (this is the case i think), you can try The Foundry's ROLLINGSHUTTER plug-in, which is more powerful. And there is a Virtualdub plugin, Deshaker, claimed to fix the rolling shutter artifacts, but i couldn't test it on my own, worth trying.
For the lens correction, there are built in stuff in AE CS6 (and probably in Premier Pro, i'm not sure though),
Effect > Distort > Optics Compensation. Play around with the
Field of View parameter along with the others. You'll have some loss in quality yet you may find the correct balance after some experimentation.
You can try first adding the rolling shutter fix, precomp the footage, then add the lens correction or vice versa.