I'm not so sure. Step 1 is making sure people want a toilet. If you give someone a toilet without their understanding its purpose, it is going to be neglected and considered pointless.

If people want toilets, they can spend some free time to dig a big pit in a nearby yard, and it will be more sanitary than their current situation. Ultimately the two go hand in hand (toilets and education) but education without toilets is a problem that solves itself, while toilets without education is doomed to fail.