I haven't done this before, but I have some ideas - even if my ideas are wrong they tend to get people talking :)

Ok so clearly you need to do the loading in a separate thread.
It should also be non-aggressive so it doesn't use all your processing and create bad frame rates. Perhaps putting a sleep(1) somewhere in your perlin generation loop would keep your game running smoothly while your game is loading.
However there may become a point where the terrain absolutely has to be loaded (such as the player is within 20 meters of it) in which case the sleep should be disabled.

Along with this you need to know exactly when to start and stop loading a chunk. The naive method for this would be something like:
if within minDistance of player startLoading
if without maxDistance of player stopLoading

stopLoading actually interrupts the perlin generation algorithm and frees up the data.

minDistance and maxDistance would be specific to how far ahead you need to load and unload your titles. We use two different values here (min, max) so that if a player dances over the threshold it is not going to start the process repeatedly loading and unloading.

I think if you only have a single core CPU you may as well do the work on the main thread - you just need to do small enough quantities of work each frame to maintain a decent frame rate.

You can estimate how much work to do each frame based on the minimum time to get to where you'll need the data (e.g. I'll need a million pixels of data in 100 frames time, so that's 10,000 pixels per frame I need to generate).

However almost everyone has a multi core CPU these days, and if you have one using a thread will be much quicker and you don't need to worry about slowing down your frame rate.