Are you aware of pg_repack [1]? I haven't had a chance to use it myself yet, but it's designed for reclaiming bloated space without downtime.
I have heard plenty of people use pg_repack so maybe it got better or we didn't test it enough.
(edit: Missed an "and")