The server could send back JSON or XML that contains two fields; percent and payload. If the percent is less than 100, your ajax client then performs the same ajax call again (you'll need some kind of request ID tracking in the request). When it is 100 you can pull the data out of the payload. The PHP of course would either return a percent less than 100 and no payload, or 100 and the full data when it's ready.
Your client ajax should be throttled to poll once every few seconds, but it sounds like that should accomplish what you want.
Edit: Incidentally, the PHP response could contain data such as how long to wait before asking again, expected time to complete, etc, as needed.