Background independence is generally the independence of the equations defining a theory on all the allowed values of its degrees of freedom, especially values of spacetime fields, especially the metric tensor. However, this concept has various levels that are inequivalent and the differences are often important to answer questions about the "necessity" of background independence, see below.
We don't know. The [manifest, see below] background independence is an aesthetic expectation, one could say a prejudice, that we cannot prove in any scientific way, so the progress in science may show that it has been a good guide or it was a misleading excessive constraint. For several centuries, we have known that science can't systematically make progress by imposing arbitrary philosophical dogmas and stubbornly defending them. Science often finds out that some philosophical expectations, however "beautiful" or "convincing", have been invalid. Expectations about the "background independence" aren't an exception. Again, it is unknown whether the final "best" form of a theory of everything (if there exists "one best form" at all, which is another albeit related "if") will be [manifestly] background-independent.
No, there's no known way to show that the lack of background independence already implies that a theory isn't a complete theory of all interactions and types of matter. Some necessary conditions for consistency may be understood in the future but at this moment, it's a speculation whether they exist.
Now, the subtleties. You implicitly wrote that string theory is background-dependent. This is a very delicate question. Some formulations (particular sets of equations used to define the theory, at least for a subclass of situations) such as AdS/CFT or Matrix theory are background-dependent. For example, AdS/CFT is formulated as a theory with a preferred background, the empty space $AdS_d\times M$, and all other states are built "on top of that". Similarly, matrix theory defines the theory for the flat space times some simple manifold (torus, K3, etc.). There is no way to see "completely" different backgrounds in this picture and even the equivalence with other nearby shapes of spacetime is far from obvious. In Matrix theory, one has to construct a new matrix model for a new background (this fact is a part of the light-cone gauge package).
However, these are just observations about what the equations "look like". Invariant statements about a theory clearly shouldn't depend on the way how equations "look like", about some possibly misleading coating on the surface: they should only depend on the actual mathematical and physical properties of the theory that may be measured. When we are asking questions about the validity or completeness of a theory, we should really be talking not about "background independence seen in the equations" but rather "background independence of the dynamics".
The dynamics of string theory is demonstrably background-independent.
This point may be shown in most formulations we know. Perturbative string theory (which requires the string coupling to remain weak and uses the weakness to organize all the around "fundamental strings" as the only elementary objects while everything else is a "soliton" or "composite") is a power-law expansion around a predetermined background but we may easily show that if we define perturbative string theory as an expansion around a different background, we get an equivalent theory. One background may be obtained from another background by adding actual physical excitations (a coherent state of gravitons and moduli) allowed by this "another background". There's only one perturbative superstring theory in this sense – whose spacetime fields may be divided to "background" and "excitations" in various ways. But the freedom to divide the fields into "background" and "excitations around it" in many ways isn't a vice in any sense. It is a virtue and, one could say, a necessity because a preferred background (identified with the vacuum ground state) is needed to describe the Hilbert space in an explicit way, approximately as a Fock space.
There is a related question whether the "space of possible backgrounds" is connected. Much of it is connected by dualities and various transitions: T-dualities, S-dualities, U-dualities, conifold and flop transitions, and various related ones that are more fancy and understood by fewer people. It's much more connected than people would be imagining in the 1980s. When we look at simple and symmetric enough vacua, they really seem to be connected: there's just one component of string/M-theory. On the other hand, the total connectedness isn't a dogma. It's a scientific – and mathematical – question whose both answers are conceivable until proved otherwise. The same equations may admit solutions that can't be deformed to one another at all. My ex-adviser Tom Banks is a defender of the viewpoint that sufficiently different backgrounds in string/M-theory should be considered disconnected although his quantum-gravity-based reasoning isn't quite comprehensible to anyone else.
When we talk about background independence, there is one more technical question, namely whether we want the theory to have the same form for all backgrounds including those that change the spacetime at infinity, or just backgrounds that preserve the fields in the asymptotic region. AdS/CFT is background-dependent in one sense because it requires the fields at infinity to converge to the $AdS_d\times M$ geometry with all the fields at their expected values (usually zero). Generally, configurations that change the asymptotic region are "heavily infinite-energy" states that can't really be constructed reliably in the original CFT. However, if you only consider backgrounds that differ in the "bulk", one could still say that even AdS/CFT (and similarly Matrix theory) is background-independent although not manifestly so.
Now, the big elephant is "manifest background independence", a form of equations that don't try to show you any preferred background at all and that are as easy (or difficult) to be applied to one background as any other, arbitrarily faraway background. All the backgrounds should emerge as solutions and they should emerge "with the same ease". This is the "manifest background independence". Some people always mean "manifest background independence" when they talk about "background independence": it should be really easy to see that all the backgrounds follow from the same equations, they think. Again, it's an aesthetic expectation that can't be shown "necessary" for anything in physics, not even the "completeness" of a theory as a final TOE.
There are limited successes. For example, the cubic Witten's open string field theory (of the Chern-Simons type) may be written in the background-independent way so that the cubic term is the only term in the action that is left. It's elegant but in reality, we always solve the equations so that we find a background-like solution and expand around it, to get back to the quadratic plus cubic (Chern-Simons-like) form of the action. While the purely cubic starting point is elegant, we are not learning too much from the first step: we're just reformulating the consistency conditions for the backgrounds as the fact that they solve some (somewhat formal) equations.
String field theory is only good to study perturbative stringy physics (and for some technical reasos, it's actually fully working for processes with internal open strings only although all closed string states may be seen as poles in the scattering amplitudes). Nonperturbatively (at strong coupling), background independence becomes harder because it should make all S-dualities (equivalence between strongly coupled string theory of one type and weakly coupled string theory of another type or the same type) manifest. Despite the overwhelming evidence supporting dualities, there's no known formulation that makes all of them manifest.
There's no way to convincingly argue that there's something wrong about this situation. In fact, one could go further. One could say that physicists have accumulated circumstantial evidence that "the formulation making all symmetries and relationships manifest" is a chimera, whether we like the flavor of these results or not. It's quite a typical situation that formulations making some features of the theory manifest make other features of the theory "hard to see" and vice versa. Because it's so typical, it could even be a "law" – a new kind of "complementarity" which goes directly against "background independence" – although we would have to formulate the law rigorously and no one knows how to do so.
For example, ordinary perturbative string theory in spaces asymptoting the 10-dimensional Minkowski space may be written down using "covariant" equations. That's the word for a description that makes the spacetime Lorentz symmetry manifest. But when we do so, the unitarity – especially the absence of negative-norm "ghost" states in the spectrum – becomes hard to prove. And vice versa. The light-cone gauge formulations make the unitarity manifest but they obscure the symmetry under some generators of the Lorentz symmetry. It's sort of inevitable.
Also, the covariant approaches (RNS) make the spacetime supersymmetry somewhat hard to prove. This "complementarity" may not be inevitable; Nathan Berkovits' pure spinor formalism, if it works and I bet it does, makes both the Lorentz symmetry and the supersymmetry manifest. It's also close to a light-cone gauge Green-Schwarz description so the "unitarity" isn't too hard, either. However, it has an infinite number of world sheet ghosts (and ghosts for ghosts, and so on, indefinitely) and one could argue that the absence of various problems connected with them is non-manifest.
The landscape of string/M-theory, as we know it today, is rather complicated and has lots of structure. We must sharpen our tools if we want to study some transitions in this landscape, a region of it. The tools needed for distinct questions seem to be inequivalent. A manifest background-independent formulation of string theory would make all these transitions equally accessible – all the tools would really be "one tool" used in many ways. In some sense, this desired construction would have to unify "all branches of maths" that become relevant for the research of separated questions in various corners of string theory (and believe me, it does look like different corners of string theory force you to learn functions and algebraic and geometric structures that are really different, studied by very different mathematicians etc.). It would be a formulation that stands "well above" this whole landscape "manifold". Such a "one size fits all" formulation is intriguing but it is in no way guaranteed to exist and failures of attempts to find it over the years provide us with some evidence (although not a proof) that it doesn't exist.
Instead, many people are imagining that string theory's landscape is a sort of a manifold that must inevitably be described by "patches" that are smoothly glued to their neighbors. Each patch requires somewhat different maths. Just like manifolds may be described in terms of an atlas of patches, the same thing could be true for the landscape of string/M-theory. We also have more unified, less fragmented ways to think about the manifolds. It's not clear whether the counterpart of these ways is possible for the stringy landscape and if it is possible, whether the human mind is capable of finding it.
So nothing is guaranteed. The transitions in the landscape and the dualities and duality groups are so mathematically diverse and rich that a formulation that "spits out" all of them as solutions to some universal equations or conditions is an ambitious goal, indeed. It may be impossible to find it.
I also want to mention one simple point about non-stringy theories. The background independence is sometimes used as a "marketing slogan" for some non-stringy proposals but the slogan is extremely misleading because instead of explaining all the duality groups in the whole landscape, including e.g. the $E_{7(7)}(Z)$ U-duality group of M-theory on a seven-torus (these exceptional Lie groups are rather complicated by themselves, and they should appear as one of the solutions to some conditions among many), these alternative theories rather tell you that no spacetime and no transitions and no interesting dualities exist at all. While their proponents try to convince you that you should like this answer, this answer is obviously wrong because the transitions, dualities, and especially the spacetime itself does exist. This version of "background-independent theories" should be called "backgrounds-prohibiting theories" or "spacetime-prohibiting theories" and of course, the fact that one can't derive any realistic spacetimes out of them is a reason to immediately abandon them, not to consider them viable competitors of string/M-theory. This version of "background independence" has absolutely nothing to do with the ambitious goal of finding rules that allow us to derive "all dualities and transitions we know in physics (not only the new, purely stringy ones but also the older ones that have been known in physics before string theory)" as solutions. Instead, this marketing type of "background independence" is a sleight of hand to argue that we should forget all the physics and there's nothing to explain, no dualities, no transitions, no moduli spaces, no spacetime. And when we believe there's nothing out there, no relevant maths etc., a theory of everything becomes equivalent to a theory of nothing and it's easy to write it down. That's a wrong and intellectually vacuous answer that should be refused, not explained or adopted.
To summarize, background independence is generally an attempt to find as universal, all-encompassing, and elegant formulations of theories, especially string/M-theory, as possible, but it is an emotional expectation, not a solid condition that theories have to obey, and we must actually listen to the evidence if we want to know whether the expectation is right, to what extent it is right, and what new related issues we have to learn even though we had no idea they could matter. It's also possible that the background-independent equations are actually "conditions of consistency of quantum gravity" (which may be written by some quantitative conditions whose precise form is only partially known): when we try to find all the solutions, we find the whole landscape of string/M-theory. Such a formulation of string/M-theory would be extremely non-constructive but after all, that's what "background independence" always wanted. Maybe we don't want too much of background independence.
