Converting character sets and foreign key constaints
Sort the ALTERs so that the FK checks will stop complaining.  Do a child before a parent (or is it the other way??).

If you have any circular references, then, yeah, remove and re-apply the FKs.

(You have pointed out yet another reason to eschew FKs.)

While you are at it, consider utf8mb4_unicode_520_ci; it comes from a newer Unicode standard.