I'm not really clear on what problem you're having here. You describe what you're doing, but then you just say that you can't use Perlin noise. Why not?
If it's just that you don't want to wait for long map generation times, then maybe you could do the top-level noise, and then do the progressively lower levels of noise only as needed? Do one Perlin iteration for the whole map, then break it into segments. Do a Perlin iteration for the segment the player is in, then break it into smaller segments, etc. down to the level of detail that you want. Keep the final results stored and mark unprocessed areas so that you don't have to repeat the work later. If you put a little thought into how you break up the segments then you should be able to amortize the work pretty effectively.