How long it takes before your script times out is an Apache configuration issue. I believe the setting is "Timeout" - add an extra zero to the current setting and restart your server. You might consider timing sections of your code and optimizing whatever is slowing everything down.

---

Update
I just reread the question, and it implies that the slow section is just basically a big string. If that's true, I don't know why it would be so slow. I stand by the Apache config, however...