Using a Mesh to make a gradient background should be very efficient. With a Libgdx Mesh you describe how much data each vertex will have (that's the `VertexAttributes` passed into the Mesh constructor) and then you provide a long list of floats that provide all that data for all vertices in one list.
I think the place to start is with the MeshColorTexture triangle from the now-classic Libgdx tutorial: http://code.google.com/p/libgdx/wiki/MeshColorTexture
. Get the "Color" example working from that tutorial, so you have a gradient-colored triangle on screen. This example passes two VertexAttribute objects that together say each vertex will have 3 position-related floats (x, y, and z), and will have 1 "packed" float for the color of the vertex. The float array passed into "setVertices" contains 12 totals floats (3 vertices with 4 floats per vertex -- x, y, z, color). The Color float is created from calling Color.toFloatBits() and passing in four values between 0 and 255 (representing red, green, blue, and alpha).
Now change that triangle into a square that fills the screen. Change the "3, 3" to "4, 4" in the Mesh constructor (since you're passing 4 vertices and 4 indices), change around the x,y,z coordinates in the float array to be the four corners of the screen (you should have a 16-element float array).
You'll need to fix the indices so they "walk" the verticies in such a way as to create two triangles (as the render() method asks OpenGL to render the Mesh as a list of triangles. So you need to walk the verticies in an "N" or "Z" order (not a "C" or "U" shape). If the indices seem odd and useless, you are correct. They're pretty useless for small examples like this, and are an API hold-over from OpenGL. You'll want to change the render method to ask to render the Mesh as a "GL10.GL_TRIANGLE_STRIP" with 4 vertices.
I'm assuming you're using OpenGL ES 1.x (not 2.0), as otherwise you'll need a shader (which is another way of creating a gradient). The Mesh API is very "close" to the underlying OpenGL APIs, so any tutorials or references you have for OpenGL (e.g., explaining vertices and indices) will help with concepts here, if not actual API calls.