My first idea is:
# deploy into public_html_new, and then:
rsync -vaH --delete public_html_new/ public_html/
A good solution were to use rsync. It changed only the really changed files. Beware, the slashes at the end ot the pathes are here important.
Normally apache don't need a restart, it is not the java world. It checks for the change of every php file on request, and rereads (and re-tokenizes) on change automatically.
Git pull were similar efficient, although it were a little bit harder to script. Of course it enabled a wide spectrum of different merging/change detection possibilities.
This solution will seamlessly only if there are no really major changes - if there are big changes in the deployment, a little bit of hazard can't be closed out, because there is a not negligible time interval, when the code will be partially changed and partically not.
If there are big changes, my suggestion were your initial solution (two rename).
Here is a little bit hardcore, but 100% atomic solution:
(1) do an alternate mount some of your filesystem, where your magento takes place:
mount /dev/sdXY /mnt/tmp
(2) do a --bind
mount of your public_html_new to public_html:
mount --bind /path/to/public_html_new /path/to/public_html
From this point, the apache will see your new deployment. Any change of a 404 is impossible.
(3) do the synhcronistation with rsync, but on the alternate mount point):
rsync -vaH --delete /mnt/tmp/path/to/public_html_new/ /mnt/tmp/path/to/public_html/
(4) remove the bind mount
umount /path/to/public_html