I don't think 16:9 is supported but you can try to use xfree86 modelines but that can be dangerous.
That other option you mentioned by scaling down the image is possible. I used it myself in the past. Atleast xine has a option to scale an image (on the fly). I thought it was the "a" button when using the official xine interface. What I did was to scale the image to 4:3 and on my tv it was then 16:9.