Diffeomorphism invariance basically means that the theory behaves the same under a coordinate change. For instance, if you take Newtonian mechanics, and replace $x \to x' = \tanh\,x$ then the equations of motion in terms of $x'$ will not be the same. In say, the usual formulation of General relativity (tensors), they will be. In other words, the theory is stated in diffeomorphism invariant terms.
But doing certain semiclassical calculations in General relativity, you are still assuming, or deriving some background (e.g., Schwarzschild metric, or perturbations around Minkowski space for gravitational radiation). This is called background dependence. On the other hand, suppose you are doing some regge calculus where you make no assumptions about what the geometry looks like (besides causality), and then sum over all possibilities and then find that one is entropically preferred, then your theory was background independent (you didn't single one out) but nonetheless you were able to derive a solution. Similarly, perturbative string theory allows you to build up your spacetime from consistency conditions and while some people like to point out that the string is quantized in "flat space", the bones of the theory itself allow for a background to develop dynamically.
I should add that for usual General relativity, solutions are very much determined by boundary conditions on Cauchy surfaces, so even if you are deriving the solution thinking that you aren't making a-priori assumptions about the space, you might be making assumptions about past infinity (like, no incoming radiation), or asymptotic flatness. These are background choices.