I haven't won religious victory yet (there always seems to be that one religion that I can't wipe off the map), but having played around a bit with apostles, I think that the best use for apostles is actually to fight combats in enemy lands instead of just spreading the religion. Offensive apostles can convert nearby cities just by winning a theological combat, and I believe that if you pick the "debater" promotion, as well as send an actual horde of them, you can destroy the enemies' defensive religious units and spread your influence without using any charge. Once the defensive apostles are wiped out, you can spread the religion the normal way.
Of course, if you lose the theological combat, it will backfire and their religion will get stronger in surrounding cities. Having a horde is important because enemy apostles can heal at their holy site, while your apostles won't be able to recover any damage. You'll have to kill them in one turn. Still, this is much better than using up your apostles' charges immediately on cities.
The bad thing about religious victory is how easy it is to defend against it right now. You don't actually need defensive apostles, just a meat wall around your cities. Actually, having defensive apostles is worse, because then enemy apostles can spread influence through killing your apostle.
Basically Firaxis needs to tweak 1UPT by allowing civilian units to stack infinitely, and to stack with foreign units during peace. Then we will have an actual religious game instead of the farce it is right now.