I've now gone through 2 months of working on that issue... several calls with AppleCare, software diagnostics tests, trying different monitors and cables, and lately: even a logic board replacement.
After AppleCare gave up, they pointed me to a local certified service center (Gravis in Stuttgart). I brought the MBA there, they tested and -with a few monitors- could affirm the problem. They then replaced the logic board (on warranty), tested again and said "fine". (By the way: after replacing the logic board, they forgot to flash the original serial number... I fixed that myself with Apple's 'blank board serializer' tool...)
Back to my workplace: tested the "new" MBA and still the same problems 😟 Not in any case better. Same flickering on external monitors. And now I tested analog output, too -- with similar problems. In comparison: my 17" Macbook Pro works like a charm on those external monitors.
Ultimately this leads me to the following conclusion: it appears to be a general problem with all new Macbook Airs that the external video signal is pretty bad. Some monitors seem to be more "forgiving" and don't show any problems (in my tests, Samsung, Apple, and NEC worked pretty okay). If you have one of those, lucky you!
Other monitors (in my tests particularly Eizo and Fujitsu) seem to be less forgiving and show intensive flickering. If you have one of those, bad luck! (Unfortunately, at my workplace we only have Eizos). A replacement Macbook Air will most likely not solve the issue for you!
Pretty disappointing... 😟