Substituting two different identifiers with the same identifier in Coq - why does this work?
it looks like we are assuming l2 doesn't change in the induction case.
  But when we later apply it with l2:=l1, we are breaking this
  assumption.


No. If we regard l1 to be a value which is repeatedly decreased in the induction proof, note that we let l2 to be equal to the initial value of l1 -- such value will not change in the induction steps. In other words: the value of l1 will decrease, but l2 will always be the initial value of l1.

We can even compare it with recursion in programming:

# pseudocode
def f(x, y):
   if x==0: return baseValue
   use f(x-1, y)
   return something


Just because f(x, y) is defined by induction on x, it does not mean that later on we can't call f(a, a) where both arguments have the same value a.