In a nut shell: Is there a way to have a specific texture bound depending on what instance is currently processed?

This idea can apply to many uses, for example a cube would only need to be uploaded once and to draw it multiple times you can use instancing and various methods to translate each cube. But my problem is that texturing each cube is a different beast. If the sampler2D has no constructor to let you choose the texture buffer of choice inside the shader, then it seems like you can only bind 1 texture for the entire instancing batch.

I've thought about rendering the instances in batches according to what their texture should be, but what if object order is important which could apply to 2D rendering with textured quads.