NoSQL : What is unstructured data?
Despite the mainstream of noSQL databases IMHO the decision about adopting such technology should be made according to the achievements needed according to the information stored, not only attending to the performance you currently have. This means that maybe your best option is to stick to the SQL database and improve your HW.

But additionally I read something in your question that made me think. There is not much about the current status of your database but your sentence "we basically store data entered by users in various ways as "key-value" lists" makes me think about if the problem wouldn't be a poor data model rather than the lack of physical resources. I've managed really large tables (+10 billion rows) with incredible performance in "traditional" SQL databases. 

I'm not saying it is wrong, just, since of course I cannot assess you in the right data model with such little information about your current solution, but just think about revisiting your data model as an additional option along with the rest since you may find some clue scratching there. 

Usually key-value lists are fine as a trade-off when you cannot implement the model in its final state because you don't know the different keys you'll have to face, or when you will need the values of one of the possible keys for a certain element. But when implemented, I usually like to re-think such decisions after a while when you have gathered enough amount of information to identify the common case of use and decide whether data model decision is the best. If you know you'll have a certain number of keys, try to do some benchmark with a design of a regular table in the traditional way

CREATE TABLE benchmarkTable (
  element INTEGER,
  key1 VARCHAR(xx),
  key2 INTEGER,
  key3 DECIMAL(5,2),
...
);


...and adding the corresponding indices. Try it out and measure execution plans with both approaches. You may be surprised specially if you gather more than one key at a time, since, among other advantages the data block size should be reduced and thus the performance would be improved.

Hope this helps, or at least broadens the possibilities and opens a new line for investigation.