What is your monitor's minimum supported scan rate?
If it goes down as far as 27KHz then you should be able to use DoublePAL (DblPAL) and have 640-720 x 512 or more, non-laced.
Ed: DblNTSC will allow the same horizontal pixels, with a few less lines, at a higher refresh.