The other solution I can think of is to use 'letterboxing', where the video is scaled to the width of the screen and because 16:9 is longer than it is tall it leaves black bars on the top and bottom called 'letterbox'. This is usually associated with cinema but it allows me to preserve the correct aspect ratio and prevent squashing the footage.
Here is an example:

The trouble is I haven't been able to successfully export my video with letterbox in After Effects. Whenever I export my video as a quicktime movie it always converts it to 4:3 even if I set the aspect ration to preserve with letterbox. This is very annoying and is forcing something that I do not want.
I have come up with a quick solution to this however. In After Effects I made a new composition with default PAL settings and nested my composition in it then scaled the footage manually to fit and have letterbox within the comp so when I export using PAL settings it will automatically be correct without any conversion or scaling done on export.