shell-exec() ist blockierend. Sprich: PHP wartet ab, bis der Befehl vollständig durchgelaufen ist, bevor es den nächsten Befehl verarbeitet. Falls dein Skript auf einem *nix-Rechner läuft (also auf so ziemlich allem außer Windows), solltest du dir die POSIX-Threadmanagementbefehle ansehen. Allerdings müssen die PCNTL-Funktionen einkompiliert sein, was sie nicht immer sind.

Alternativ kannst du dir vielleicht mit proc_open() was basteln, allerdings hab' ich auf die Schnelle nichts sinnvolles hingekriegt.