In my settings for my SPA-3102 gateway, there is a setting for one stage dialing. I have not used it, but when I have, it sounds similar to what you would want. It was a little rough around the edges because I did not make a dial plan so that dialing 0 would automatically send the phone to the pstn gateway. However, if you look on your gateway and find a setting for staged dialing, it would be a matter of making an outbound rule for calls beginning with 0 to go to a certain gateway, setting up a dial plan on the phone so that 0 is sent right away, and then lastly dialing the external number and hitting #, dial, or adding a dial plan depending on your phone.
Please let us know what gateway you're testing on and how the tests go!