fork is your friend. Fork off a copy of your script and have it do whatever it needs to do. A fork + exec may be better, if you want to do something else in its place.
Caveat - if you're running in a mod_perl environment, you're gonna fork your entire apache process, which has memory overhead concerns among other issues that I always seem to forget. Filehandles, is it? Only do it here if you absolutely have to. CGIs? No sweat.
From there, just proceed as before - refresh the user back to some other page, and when your forked process completes, give it someway to flag its being finished. Touch a file, update a row in a database, something. Something that can be a quick and simple check for the front end to do.
To show the user the changes, there are several approaches - have 'em constantly click a button ("Am I done yet?") to refresh the page and display results if appropriate. Or bring up a "loading..." screen that watches for the update and refreshes when it gets it (note that this blocks the user), or do something fancy and ajaxy that autorefreshes (or gives a refresh button) when the data is actually there.