You're not going to get an acceptable solution for this that doesn't involve some kind of shader - what you're talking about is a dependent texture read and that needs shaders (or some other kind of per-fragment programmability). The only way I can think of would be to tesselate your geometry really really heavily (such that one triangle approximately maps to one pixel), keeping the noise texture in system memory, and doing your coord modification per-vertex. That's not going to run well at all - a combination of heavy tesselation and needing to resubmit all the texcoords for it every frame will pull down performance badly.

So, on to shaders.

The main question I'd ask is "are you really certain that you need to run on hardware going back to the year 2000?" That's 12-year old hardware now, and assuming that you can even find any that still works, would somebody who's clinging on to such ancient junk even be considered part of your target audience? On the surface, it has to be said, you seem to be being a great deal over-conservative here, and that's a requirement that I seriously recommend you rethink.

Let's move on and assume that some kind of shader support is acceptable as a baseline requirement.

Here we have a number of options. Something like the old NV register combiners would work if you really want to target older hardware, but they're not going to be so broadly available. ARB assembly programs are another option (moving up a little more) and they will meet your requirement while still maintaining very broad hardware compatibility - even integrated Intels from 6 years back will support them. They are more limited (and more complex to write - although the C interface is simpler) than GLSL however. And that brings us to GLSL itself where the compatibility problem is really not so bad. Shooting for something like the GL 2.1 version of GLSL will give you very good hardware compatibility across the vast majority of hardware you'll find in people's machines today - it's only the really old integrated Intels I mentioned before that won't support it (more recent ones do) so the question changes to one of "do you need to run on ancient integrated Intels?"

Bear in mind here that these Intels were really only ever found in business PCs, laptops, and el-cheapo high-street "multimedia" PCs and it comes back again to you needing to think more about who your target audience are. That's the first thing you need to define before any definitive recommendation on how to go forward can be given.

Assembly programs are going to remain supported for quite some time yet - reason why is that Doom 3 used them, so no hardware vendor is going to be too willing to drop Doom 3 support.