How do I get Mathematica to return a function call unevaluated?

Here's how this can be done:

ClearAll[algebraicQ]
algebraicQ[x_] := Module[{result},
  result = Element[x, Algebraics]; 
  result /; MatchQ[result, True | False]]

The key to these types of problems is usually a special use of Condition inside Block/Module/With which allows sharing localized variables between the condition and the body of Module.

---

At this point I should note that the convention seems to be that any function that ends in ...Q will always return either True or False. Consider EvenQ vs Positive. EvenQ[x], with x undefined, gives False. Positive[x] stays unevaluated. I know of only a very few edge cases which don't follow this. Naming this algebraicQ would violate that convention.

Your earlier approach would have worked if you had actually tested the argument to the function (a) rather than the undefined symbol x...

AlgebraicQ[a_] := True /; Element[a, Algebraics]
AlgebraicQ[a_] := False /; ! Element[a, Algebraics]
AlgebraicQ /@ {7, Pi, Pi + E}

(* {True, False, AlgebraicQ[E + Pi]} *)