How to properly inject iterators into table?

General

I think that one can achieve the goal much easier if we reformulate the request. A variable is IMO not a proper object to store an iterator in the form of expression. What you really need is an environment, which would use certain iterator in code.

Simple lexical / dynamic environment

Here is how it may look:

ClearAll[withIterator];
SetAttributes[withIterator, HoldAll];
withIterator[{var_Symbol, iter__}] :=
  Function[ 
    code,
    Unevaluated[code] /. var :>  Sequence@iter,
    HoldAll
  ];

This is a lexical scoping construct, which binds the variable var lexically to the iterator(s) you may want to use. Now, for your particilar iterator, we construct a custom environment and store it in a variable:

iterEnv = 
    withIterator[{
      iter, 
      {a, {1, 2, 3}}, {b, Complement[{1, 2, 3}, {a}]}, {c, Complement[{1, 2, 3}, {a, b}]}}
    ];

You can now use this with any code, just using the iter variable there:

iterEnv@Table[{a, b}, iter]

(* {{{{1, 2}}, {{1, 3}}}, {{{2, 1}}, {{2, 3}}}, {{{3, 1}}, {{3, 2}}}} *)

So, the resulting environment is half-lexical and half-dynamic. You do store it in a variable, but what you store is a full environment (a function, closure), rather than just an expression for an iterator.

Another version of a lexical environment

The above version has a flaw that the lexical binding for variable iter is broken into two different pieces of code - the environment proper and the call. For better readability, and robustness, it is better to have a fully lexical environment, where the variable is bound to a value at the same piece of code, so the binding is transparent.

Here is a way to do this. First, we define a generator for environments:

iterEnvironmentGenerator = 
   Function[Null, Function[var, withIterator[{var, ##}], HoldAll], HoldAll]

Now, the fully lexical environment:

ClearAll[withIteratorLex];
SetAttributes[withIteratorLex, HoldRest];
withIteratorLex[env_Function, {var_Symbol, code_}] := env[var][code]; 

Here is how it can be used. First, you create an environment, using a generator:

env = 
  iterEnvironmentGenerator[
     {a, {1, 2, 3}}, 
     {b, Complement[{1, 2, 3}, {a}]}, 
     {c, Complement[{1, 2, 3}, {a, b}]}
  ];

Now you call:

withIteratorLex[env, {it, Table[{a, b}, it]}]

(* {{{{1, 2}}, {{1, 3}}}, {{{2, 1}}, {{2, 3}}}, {{{3, 1}}, {{3,2}}}} *)

The bindings for a and b remain split between env and the code in Table, but they are dynamic anyway, so this is kind of ok. But the binding of it is now fully lexical, which is certainly a plus.

Remarks

The conclusion seems to be that the complexity of the solution directly depends on how the code is split into part / building blocks. To quote John Hughes ("Why functional programming matters"), "Our ability to decompose a problem into parts depends directly on our ability to glue solutions together". Mathematica provides various ways to glue things together, and depending on our choice of building blocks, the composability of them is different.

Philosophically, the problems with the original approach were mostly because you tried to break the code into pieces which, in the context of iterators and variable bindings, do not make sense by themselves, and therefore require extra trickery on every invocation. As a rule, it is better to incapsulate the process of variable binding together with a piece of code, rather than doing tricks with scope surgery and evaluation control to de-facto implement binding at the moment when you call your code. To put it differently, scoping constructs nest and compose well, so whenever the problem asks for it, it may be a good idea to create one.

Not sure if this fits your needs:

z2 := Sequence[{a, {1, 2, 3}}, {b, Complement[{1, 2, 3}, {a}]}, 
               {c, Complement[{1, 2, 3}, {a, b}]}]

Unevaluated @ Table[{a, b}, z2] /. OwnValues @ z2

{{{{1, 2}}, {{1, 3}}}, {{{2, 1}}, {{2, 3}}}, {{{3, 1}}, {{3, 2}}}}

You can use z2 with Set here too:

z2 = Unevaluated @ Sequence[{a, {1, 2, 3}}, {b, Complement[{1, 2, 3}, {a}]}, {c, 
                             Complement[{1, 2, 3}, {a, b}]}]

---

---

If you don't want to use Sequence in z2 then maybe:

z2 = Unevaluated @ {{a, {1, 2, 3}}, {b, Complement[{1, 2, 3}, {a}]}, {c,
 Complement[{1, 2, 3}, {a, b}]}};

Unevaluated @ Table[{a, b}, z2] /. ReplacePart[OwnValues[z2], {1, 2, 0} -> Sequence]

{{{{1, 2}}, {{1, 3}}}, {{{2, 1}}, {{2, 3}}}, {{{3, 1}}, {{3, 2}}}}

Would this work for you?

m = Sequence @@ MapThread[{#1, comp[#2, #3]} &, {vars, cr, varsx}];

tab[vars, m] /. {tab -> Table, comp -> Complement}

(* {{{{{2, 1, 0, 3}}, {{2, 1, 3, 0}}}, {{{2, 3, 0, 1}}, {{2, 3, 
     1, 0}}}}, {{{{3, 1, 0, 2}}, {{3, 1, 2, 0}}}, {{{3, 2, 0, 
     1}}, {{3, 2, 1, 0}}}}} *)