evaluation - How to properly inject iterators into table?

Goofing off on a prior question, I was fiddling with other methods, which led me to the need to inject a constructed set of iterators into a table construct.

Now,

ClearAll[a, b, z, z2]


z = {{a, {1, 2, 3}}, {b, {1, 2, 3}}}
Table[{a, b}, Evaluate[Sequence @@ z]]

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

Precisely what I'd expect. What I've been trying to inject is of the form:

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

It seems whatever combinations of Hold, Unevaluated, etc. I wrap this in (so the Complement doesn't get immediately evaluated), it doesn't make it through injection: I get results as if the complement is not there. I know it is, since changing the second argument to Complement to something invalid throws an error in the Table evaluation and shows it in the error information.

I'm guessing the iterator variables I'm using in the second arguments to the Complements are just getting eval'd as the symbol name, so the Complement is the complete first argument since there's no overlap.

I'm stumped. Any suggestions?

Update: Playing around with Kuba's interesting answer, and getting there, but still some issues. Here's a snippet of some pieces to show what's happening:

t = 4
c = {0, 0, 1, 2}

cr = Reverse@Range[c, t - 1];
vars = Unique[] & /@ Range@t
varsx = Map[vars[[;; # - 1]] &, Range@t];


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

res = Unevaluated[ReleaseHold@Table[vars, m]] /. OwnValues[m];

I create the ranges for each iterator in cr, the variable each corresponds to in vars, and the list of what's to be complemented in varsx.

The map creates the list of {iterator var, Complement[interator range, prior iterators]}... In this example, I've used HoldForm to prevent immediate evaluation of the Complement, but as I said, I've tried various incantations.

In any case, the correct desired results show up in res using Kuba's technique, despite MMA complaining about malformed iterators.

Update: Thanks to all for the enlightening answers. All were useful an interesting, and picking an accept was troublesome: I picked LS's becuase his answer is the "proper" way to do such things, but that does not reduce the value of all the other answers to me.

I'd advise readers to look at all of them...

Answer

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.