As a proof-of-concept for the rendering of labels on demand I set up an OpenLayers map with two XYZ tile layers, one for the background and one for the labels. I configured the MapQuest render stack to deliver those two layers, the background layer is stored in the tile store, the label layer is never stored, but always rendered on demand.
As the Mapnik configuration for these two layers I used the MapQuest style as base. In the background layer I removed everything that has to do with labels and put those things into the labels layer.
To speed things up, I created a copy of each of the data tables in the database which contains only entries WHERE name IS NOT NULL OR ref IS NOT NULL. I added those tables to geometry_columns and added indexes. And I pointed the layer definitions in the labels map style to those new tables.
The result, while not being fast, is not horribly slow either. Actually quite usable. Of course I used the data for a part of Germany (Baden-Württemberg) only. And I am the only one accessing the server.
So this doesn’t tell me that this approach can work, but at least it seems to be an option. There are a lot more optimizations that can be done. The biggest one would be to store the metatile at least for a small amount of time. At the moment the complete metatile with the labels is rendered every time a tile is accessed.
Comments can be directed to the Multilingual maps wiki page.