Identify the independent variable in an expression

As Daniel Lichtblau points out in the comments, it's a scoping problem. From the documentation:

The named formal parameters xi in Function[{x1,...}, body] are treated as local, and are renamed xi$ when necessary to avoid confusion with actual arguments supplied to the function.

You can get around this in several ways:

1. Although I don't recommend it, you can explicitly supply x$ as the variable in expr:

   formalLimit[x$^2, 2, 4, .1]
   

   4

   This will not solve your second problem.

2. A better way is to rewrite formalLimit to take an extra argument specifying the variable for which the limit is being taken:

   formalLimitMk2[expr_, var_, a_, L_, \[Epsilon]_] := Module[{f},
     f = (expr /. var -> Slot[]) &;
     f[2]
    ]
   
   formalLimitMk2[x^2, x, 2, 4, .1]
   

   4

3. If your functions will all have only one variable, you can use Variables to extract it:

   formalLimitMk3[expr_, a_, L_, \[Epsilon]_] := Module[{f},
     f = (expr /. First@Variables@expr -> Slot[]) &;
     f[2]
    ]
   
   formalLimitMk3[Sqrt[4 - t^2], x, 2, 4, .1]
   

   0

   Variables is described in the documentation as working for polynomials.

Use an optional argument for the variable with a default of x

Clear[formalLimit]

formalLimit[expr_, a_, L_, ϵ_, sym : _Symbol : x] :=
 Module[{f}, f[y_] := expr /. sym -> y;
  f[2]]


formalLimit[x^2, 2, 4, .1]

(*  4  *)

formalLimit[z^2, 2, 4, .1, z]

(*  4  *)

I would approach of problem of giving students a formal limit evaluator from a different point of view. I would write a multivariate formal limit evaluator and specialize for the single variable case. Since I have a version of Mathematica that is later than V10.1, I would make use of the fairly new ContainsAll function.

formalLimit[expr_, x_Symbol -> val_] := formalLimit[expr, {x -> val}]
formalLimit[expr_, rules : {(_Symbol -> _) ..}] :=
  (expr /. rules) /; ContainsAll[Cases[expr, _, ∞], rules[[All, 1]]]

With these definitions, the following evaluations succeed.

formalLimit[1/x, x -> ∞]

0

formalLimit[Sqrt[x^2 + y^2], {x -> 3, y -> 4}]

5

But these evaluations fail as they should,

formalLimit[Sqrt[x^2 + z^2], {x -> 3, y -> 4}]

formalLimit[Sqrt[x^2 + z^2], {x -> 3, y -> 4}]

formalLimit[Sqrt[x^2 + y^2], {x -> 3, z -> 4}]

formalLimit[Sqrt[x^2 + y^2], {x -> 3, z -> 4}]

With[{x = 42}, formalLimit[Sqrt[x^2 + y^2], {x -> 3, y -> 4}]]

formalLimit[Sqrt[1764 + y^2], {42 -> 3, y -> 4}]