You should actually crop it the way you want and use CS4's content aware skewing to stretch or shrink parts of the image. Just be sure it does it correctly and doesn't look ridiculous lol....

don't know why I didn't think of it earlier. It's like auto cloning!