Another possibility is to just avoid gendered public restrooms, like I do. There are some gender-neutral toilets (for instance, in trains which I use very often, and at friends homes, at some trans*-friendly places, etc.). Society just doesn't want me (who doesn't seem to be part of "them") to use "their" public toilets, so I either have to shut up and manage my toilet usage, or to degrade myself and/or risk mental and physical violence. At the moment, I go with the first solution most times. (And thanks to all people who push ahead two-gender-separated toilets.)