Добрый день.

Посоветуйте NoSQL key/value базу с поддержкой составного ключа и с клиантам для java.

memcache.

А если надо хранить -- то mysql.

Возможно немного поздно, но могу посоветывать CouchDB. Она легка в обращение и удобна. Существует множество клиентов для джавы, из тех с которыми работал могу порекомендовать ektorp и jzboy. Jzboy более минималестический, ektorp - клиент с большой функциональностью.