If you were using GL 3+, you can utilize geometry shaders and instancing.
But really there is no need to restrict your audience to GL 3+ (it's not yet very widely supported, especially not in the casual market). GL 2+ functionality will be more than enough for a 2D sprite batcher.
The simplest way to optimize your sprite batcher is to send as little as possible to GL. Update your uniforms (e.g. ortho 2D projection matrix) only as necessary, and only pass the attributes you really need. If you know some of your data is static, you can use multiple VBOs, otherwise you should just stick to interleaved data.
My sprite batcher uses the following attributes per vertex:
{ x, y, color, u, v }
The color is a packed float. That means 5 attributes per vertex, and 4 vertices per sprite using element indices. One-off transformations (like sprite rotation) are done in CPU before passing vetex position.
Most of the time, optimizing in 2D is more about using texture atlases, improving batch rendering, and minimizing overdraw rather than worrying about small things like whether or not to interleave your VBO data. Besides, 99% of the time a 2D game will become fill-rate bound before it becomes vertex bound.
On the subject of fill rate, you can use hexagons or some other non-rectangular primitive as an optimization (although it comes at the cost of more vertices and may be undesirable depending on you sprites).
For more reading on my sprite batcher:
https://github.com/mattdesl/lwjgl-basics/wiki/Sprite-Batching
https://github.com/mattdesl/lwjgl-basics/blob/master/src/mdesl/graphics/SpriteBatch.java
Using plain old VBOs or even vertex arrays will be plenty fast, but if you want to squeeze a bit more performance out of GL 2.0 you should look into mapped VBOs:
http://www.java-gaming.org/topics/opengl-lightning-fast-managed-vbo-mapping/28209/view.html