In an ideal world yes but in so many places this just won't be possible. I think we need solutions that work within existing facilities.
Not wishing to be rude, but actually its very possible, and the blueprint already exists in all local authorities from enforcing the creation of accessible disabled toilets. That took maybe five years from nothing to standard and everywhere.
stage 1) legal bill requiring it, all new builds only passed if holding single sex AND unisex facilities, size of building, budget and number of users taken into account in expectations of what should be provided proportionally, and how quickly.
stage 2) Local Authority sort out funding grants for public places like schools, churches, village halls, etc, make it part of their inclusion brief for staff to go out and advise and gently deal with the kick off about we can't do it, there's no room, there's no budget. All of that happened with disabled loos, once everyone realised they did have to do it, budget would be found and helped where necessary they got on with it. Those LA staff also provide the expectation and legal back up of this isn't optional.
stage 3) as with other accessibility things such as trains, buses, disabled changing facilities, ramps, pavements kept clear for wheelchairs, it takes banging on, persistence and the gradual realisation that you don't want to get sued for lack of accessibility.
The disabled lobby did not have massive, government funded, very wealthy political lobby groups with the direct ear of government, all political parties lining up to help, half the businesses of the UK labelled 'disability champions' with their status based on following a political lobby's expectations, the massive ear of the press, a lot of wealthy donors and a fuckton of women desperate to just be left alone rather than be excluded from single sex spaces. This could very easily and quickly be achieved, if it was a wanted outcome.