Well the 504 timeout is coming directly from the server. The rebuild process will be time/CPU (and possibly memory) intensive, but it shouldn't wholly block other connections. If it is, it sounds like only one PHP process is being processed at a time (no task switching), which is likely to give bad performance in general. I'm guessing you're using a FastCGI server so you may want to look at that configuration (the number of processes/children available).
Otherwise, 1.2 would help. It doesn't inherently change the amount of work that needs to be done -- there is a lot of recalculation to do -- but it's designed to allow that work to be split into multiple steps.