Polymorphic STL foreach without passing the container type
This line gives my nightmares:

std::unordered_map&lt;void *, bool&gt; _advance_iterator__instances_done;


First up the name is reserved. Prefer not to use identifiers without a leading underscore (the rules are not trivial and everybody gets them wrong so just avoid them).

Secondly the size of the map is unbound. If you have a really large application (runs a long time) this is going to continuously grow.

This construct

bool advance_iterator(Tc &amp;container, Ti &amp;iterator)
{
   static typename Tc::iterator it;


makes the whole thing not thread safe.

Your naming convention makes it confusing to read:

#define foreach(value_type, iterator, container) \
                           ^^^^^^^^^^^
                     This is never the iterator it is the value.


Overall I think the boost FOREACH is a better choice for C++03 and C++11 now has a built in version