For a non-shader solution you could draw in two batches. First of all you flag the cubes in the current scene that need the overlay texture - this can be done during your scene tree traversal or other scene setup. Then draw the regular cubes using your normal draw routine. Finally draw the overlay-textured cubes using multitexturing - you can experiment with a decal or interpolate TexEnv for this.
The VBO setup would just use the same set of texcoords for both texture units; something like this (not intended as copy-and-paste code):
glClientActiveTexture (GL_TEXTURE0);
glEnableClientState (GL_TEXTURE_COORD_POINTER);
glTexCoordPointer (2, GL_FLOAT, sizeof (myvertextype), (void *) 12);
glClientActiveTexture (GL_TEXTURE1);
glEnableClientState (GL_TEXTURE_COORD_POINTER);
glTexCoordPointer (2, GL_FLOAT, sizeof (myvertextype), (void *) 12);
// drawing stuff
glClientActiveTexture (GL_TEXTURE1);
glDisableClientState (GL_TEXTURE_COORD_POINTER);
glClientActiveTexture (GL_TEXTURE0);
glDisableClientState (GL_TEXTURE_COORD_POINTER);
But otherwise - yeah - the shader-based solution would be preferable. Aside from those ClientActiveTexture calls going away (which is always a good thing) you've got much better control over the type of blend you do between the two textures.