Regarding atyy's second set of questions:
For the original example of AdS/CFT (stack of D3-branes), the string theory and the gauge theory are perturbatively calculable in different parameter ranges.
http://www.springerlink.com/content/9p632240j7314480/" (section 3.5):
the string theory on AdS5 x S5 is currently only really calculable in the classical supergravity limit where gs << 1 (so no string loops) and ls >> R (so no alpha' corrections). In terms of YM parameters this means that N >> lambda >> 1, which is the planar ’t Hooft limit, but at strong ’t Hooft coupling. On the other hand, the YM theory is only under perturbative control at small lambda and finite N. A great deal of the power of Maldacena’s conjecture comes not just from the fact that it is an explicit realization of the AdS/CFT conjecture, but also that weak coupling on one side of the equivalence is strong coupling on the other.
Because one is varying several parameters here - rank of the gauge group (N), coupling constant (g, where g
string = g
Yang-Mills2) - or even their product - lambda, the 't Hooft coupling, is g
stringN - it can be hard to keep track of the relations between these limits. But maybe the important conceptual question, for the present discussion, is whether the existence of a calculable framework on one side of the duality implies the existence of a "classical limit" on the other side of the duality. I suppose the answer is "yes", but to visualize or comprehend this limit, you have to use the variables on the other side of the duality.
So maybe the best initial answer to atyy's challenge - how can these SCFTs not have classical limits when they are dual to classical supergravity in the bulk - is that, yes, these SCFTs do have classical limits where they "shouldn't", but the only classical characterization of those limits is precisely in terms of the dual, bulk variables (which can all be defined by the right combinations of operators from the boundary theory). You wouldn't be able to see it if you were just looking at the "original" variables.
Now, returning to John Schwarz's talk, the three primordial examples of AdS/CFT are for D3-branes, M2-branes, and M5-branes. In every case, you have a stack of coincident branes with a worldvolume theory that is decoupled from space-time far from the branes (think of the causally disconnected regions that can show up in Penrose diagrams), and the worldvolume theory is equivalent to string theory in an AdS space. For strong gravitational back-reaction, such that the branes form an event horizon, AdS is the actual near-horizon geometry. For weak gravitational back-reaction, such that the branes are existing in flat space, the AdS space seems to exist as a manifestation of energy scale in the worldvolume theory, akin to Guifre Vidal's MERA construction (but this is one of the conceptual issues that is still being worked out). So whether you're at weak or strong 't Hooft coupling, AdS is there.
For D3-branes, I quoted Argyres on how perturbative limits exist in two distinct parameter ranges that lie on opposite sides of the duality. As Schwarz says, for some time it was believed that the worldvolume theories for M2- and M5-branes were non-Lagrangian, meaning that there was no perturbative formulation. Following the discussion in previous comments, this would have meant that the only classical limit for this quantum theory was in terms of bulk variables, like supergravity. But ABJM showed that the M2-brane worldvolume theory was a super-Chern-Simons theory, and the Chern-Simons level "k" was able to play the role of Yang-Mills coupling g
YM, so there's a 't Hooft coupling for these theories, kN.
The remaining question is whether the M5-brane worldvolume theory also has a perturbative formulation, or whether it really is non-Lagrangian. ("Always strongly coupled" must mean that the parameter, which you might have wanted to use for a perturbation expansion, remains large at every energy scale - there's nothing like asymptotic freedom.) And this is the subject of ongoing research.