I'm afraid adding a Web Service layer is probably the correct solution to your problem.
Separating the client from the underlying database implementation will probably help you in the long run too.
Adding a web service layer doesn't necessarily have to hurt performance...
Indeed, with an appropriate API, a web service can actually improve performance, by batching together multiple database queries within the data center LAN, rather than requiring multiple round trips over the WAN.
And of course a web service layer can often be scaled horizontally, and add appropriate caching to your database queries, perhaps even a change notification mechanism.
A server layer adds security that you cannot possibly ensure with apps running on a remote client. Anything that runs on a client can be "hacked" and should not really be considered in any way trusted. You should only really put presentation logic in the client, and host anything important on hardware you have complete control of.
I don't know about your apps, but my web apps are naturally split into several layers, with the presentation code separated from the persistence layer by at least one level of business logic that keeps the two apart. I find this makes it much easier to reason about my app, and so much faster to add or modify functionality. If the layers are separated anyway, it is relatively easy to keep the presentation layer in the client, and the rest on a server under my control.
So while you can solve your problems without introducing a "web service" layer, by the time you have written all the stored procedures (or equivalent) necessary to fill in the holes in the standard database security implementation, you would probably be better off writing a server-side application that you can write proper unit tests for.
While I agree with your premise that NoSQL is not a panacea for all database woes, I think you misunderstand one key point.
In NoSQL database you have only one criterion you can search for effectively - the key.
This is clearly not true.
For example MongoDB supports indices. (from https://docs.mongodb.org/v3.0/core/indexes-introduction/)
Indexes support the efficient execution of queries in MongoDB. Without
indexes, MongoDB must perform a collection scan, i.e. scan every
document in a collection, to select those documents that match the
query statement. If an appropriate index exists for a query, MongoDB
can use the index to limit the number of documents it must inspect.
Indexes are special data structures [1] that store a small portion of
the collection’s data set in an easy to traverse form. The index
stores the value of a specific field or set of fields, ordered by the
value of the field. The ordering of the index entries supports
efficient equality matches and range-based query operations. In
addition, MongoDB can return sorted results by using the ordering in
the index.
As does couchbase (from http://docs.couchbase.com/admin/admin/Views/views-intro.html)
Couchbase views enable indexing and querying of data.
A view creates an index on the data according to the defined format
and structure. The view consists of specific fields and information
extracted from the objects in Couchbase.
In fact anything that calls itself a NoSQL database rather than a key-value store should realy support some kind of indexing schemes.
In fact, it is often the flexibility of these index schemes that makes NoSQL shine. In my opinion, the language used to define the NoSQL indices are often more expressive or natural than SQL, and since they usually live outside the table, you don't need to change your table schemas to support them. (Not to say you cant do similar things in SQL but to me it feels like there is a lot more hoop-jumping involved).
Best Answer
Disclosure - I'm working for ScaleBase - who builds a transparent Database Sharding solution.
I don't really think those two terms have allot to do with one another. To scale relational databases (a.k.a SQL databases) you usually use sharding. But, if you don't need relational database, you can use NoSQL solutions, some of which are key-value based (like the popular Cassandra, but see here for more).
So the first is a solution for database scaling, the second is a relational database alternative.