This is an entirely hypothetical question, I'm not in this situation now.
What happens to your VLAN topology and routing if you run a multi tenant network and you have more than 4096 customers?
Do you have to start "zoning" your network at the highest level in to new trees of routers/switches and start again with reusing VLAN numbers?
You either use Q-in-Q, or yes, you build out a second isolated switch forest with it's own set of VLANs.
Consider looking at some modern switching technologies even if it's just for comparison's sake - for instance VPLS (Virtual Private LAN Service).
Juniper have a really interesting paper on datacenter VPLS at http://www.juniper.net/us/en/local/pdf/implementation-guides/8010050-en.pdf .
One key advantage to offering VPLS over VLANs, is that in a VPLS network, you deal with MPLS labels rather than VLAN IDs, so you can potentially scale to tens of thousands of VPLS instances.
Another key advantage, is that if all your switches are participating in the same MPLS network, you can simply configure a VPLS instance at the two edge switches facing your customers - that is, your source port and your destination port - and you don't need to 'plumb' VLANs between your edge switches and core switches. This saves a LOT of time in provisioning, especially as your network grows.
You can also configure multiple MPLS paths between switches, which means it's possible to build a 'mesh'-style switching environment which can tolerate failure of switches - even core or aggregation switches.
You may not be at the point where you can pull off an MPLS-capable switching network yet. But if you truly intend to scale - this could be a better solution than a pile of Q-in-Q.
Of course there are disadvantages - you'll likely need some nice switches (for instance Juniper EX3200, Cisco 3750, or better).
There are other technologies available as well, for instance Cisco/Brocade TRILL, or Juniper QFabric (I'll let you Google for these) - but these are probably reserved for the fat cats with large datacenters, who will roll out a full network as a new investment, rather than a 'small' guy trying to organically grow his business.
One last piece of advice: Carefully, carefully think about how you might prevent switching loops when offering either Q-in-Q or VPLS links to a customer. And run some scenarios in advance. :-)