Texture binding problem with Vertex Arrays

Well i am working on this 2D game like Age of Empires.I need to bind different textures depending on the type of terrain stored in a map. But i store the texture co-ords for all positions in the map in an array and then call glDrawElements() to use the Vertex array.
I just realized that even though i have stored the texture co-ordinates in the vertex array i cant change the texture after calling glDrawElements. Its a funny problem since i dont want the same texture covering the whole screen… being drawn for all the tex-coordinates in the array.Yet i know i cant change the texture binding when using vertex arrays. I do want to Optimize my code but it seems i cant use VAs like this…is there a work around ? Displays lists ? i have been advised against them !!

Bind the texture, then draw, bind the texture, then draw…

for(i=0; i<xxx; i++)


set up your arrays with glVertexPointer, etc
and enable them