Indirect texture lookups are supported by all hardware that implements GLSL (and even by GL's predecessor assembly shader language).
In early shader models there was a limit to the number of indirections you could perform (e.g. at most, you could do 4 indirect lookups in a single invocation) but modern hardware no longer suffers from any such limitation. This is even less of an issue since your question mentions this is a vertex shader that you are doing the texture lookups in. Vertex texture fetches are a Shader Model 3.0 feature.
As for doing this efficiently, that is a different story. Generally dependent lookups are not cache/pre-fetch friendly, but sometimes if the access pattern (e.g. monotonic coordinate change) is correct this is less of an issue.
An interesting point to note is that any time a texture coordinate is computed (as opposed to taken directly from a per-vertex / per-fragment input) while the shader is being invoked, it is technically a dependent lookup. You do not need to fetch something from another texture in order to create this situation (though this is most often what people associate with dependent).