While it’s really not possible to do what you want in the way your boss is asking, you could look at using an app like iResizer. While it won’t completely solve your problem, it might get you closer to what your boss wants.
I’ve used it on several projects before with great results, and my end clients were very happy with what they thought they wanted.
If you do try the iResizer app, you will want to try resizing each image several times with different maskings (masks are used to define areas that will not distort when the image is re-sized), then choose the best result out of about 3 or 4 different run throughs.
Also, you might want to let your boss know that raster images (pixels based, photos, scanned images, images created within Photoshop) are not vectors (what you would create in Illustrator) and as such will typically suffer from some distortion when upsized.