You will need to crop away (i.e. leave out) the parts of the photo you don't want in order to make it fit the 3:2 (or whatever) aspect ratio. So if you have a 1600x1200 image, you will generally need to eliminate some pixels along the shorter axis to make it a 1600x1067 image. The same goes for other aspect ratios, eg. 8R's 4:5 ratio. Don't just resize in Photoshop with "constrain proportions" off, because it will definitely distort the picture, as you mentioned, unless you like that kind of effect.
Alternatively, you can just send the full image in to the shop and specify whether you want it printed as a cropped image or in its entirety. In the former case, the lab will then do the cropping based on their own judgment (may not always be to your liking, though), while in the latter case, the lab will print the whole 4:3 picture but leave white unprinted borders in the 'excess' space, which you can then cut off yourself later on.