Well, how frequently do you go beyond 512x512? And why not use a larger texture, like the largest the device supports (if you need it that big, that is)? If you are having a hard time fitting so much in the atlas, though, just put less stuff in it. For example, use only the textures on the given map, and create an atlas per layer.
The benefit comes from batching more than the texture switching. As long as you are still sending a few thousand primitives per call, then yeah, you will gain benefit. Also, I don't see why it would make it any less flexible, and the complexity of it can likely be almost completely abstracted.