I hate it when speakers talk about "NoSQL" without specifying what they are actually bitching about, which in this case is clearly Key-Value/Document oriented databases.
Of the non-relational databases, there are actually many which provide everything you want in a relational DB (separation of logical and physical within the DB) as well as storing the schema as PART of the data instead of a physically configured separate entity. These databases are called graph databases, and they are awesome. I am convinced they would have been the major databases of today, if not for the fact that it takes way more computing power and fancy algorithms to work with graph data models.
The real problem with graph databases is that they do not scale because the algorithms used parallelize poorly. Partitioning graphs is a longstanding challenge in computer science.
It is literally equivalent to the NoSQL "we don't do joins" algorithm problem. Unlike most NoSQL databases, the basic operation of a graph database is built on join algorithms (edge traversal is a relational join). If you figure out how to parallelize ad hoc joins on large clusters then graph databases become a viable solution for non-trivial databases.
