Is there any efficient way to fetch texture data in a random way? That is, I'd like to use a texture as a look-up table and I need random access to its elements. Therefore I'd be sampling it in a random fashion. Is it a completely lost cause?
Random access is a basic feature of GLSL. E.g.
vec2 someLocation = ... whatever you like ...; vec4 sampledColour = texture2D(sampler, someLocation);
Depending on your hardware, it may cost more to read a texture if you've calculated the sample locations directly in the pixel shader rather than out in the vertex shader and allowed them to be interpolated automatically as a varying, but that's just an immutable hardware cost relating to the decreased predictability of what you're doing.
You could always pass another texture to the shader containing random values and sample from that. That will give you the same random value for each texture coordinate but if you dont want that you can always multiply the coordinate by a uniform seed that you updated each frame.