Yes, that was one other attempted solution: to sort of alternate "he" and "she." It's fascinating to watch the cycles of proposal/resistance, proposal/resistance... The reason I feel like singular "they" is going to succeed is that the usage is mostly unconscious, unintentional - people don't even know they're doing it. So that sounds like a done deal to me, though resistance in academia, in particular, is ferocious.
p.s. I just Googled "no one in their right mind" and 23,300,000 usages come up; and got a form from my son's school: "If you wish your child to participate, please complete the permission slip and return it to their teacher by Friday."