I'm looking for a distributed cache for key-value pairs with these features -
What are the databases that fit the bill?
There are a lot of options that you can make use of.
Redis - the one you've stated by yourself. Its a distinct process, very fast, key-value for sure, but it's not an "in-memory with your application", I mean that you'll always do a socket I/O in order to go to redis process. Its not written in Java, but it provides a descent Java Driver to work with, moreover there is a spring integration.
If you want a java based solution consider the following:
memcached - a distributed cache
Hazelcast - its a datagrid, its much more than simply key-value store, but you might be interested in this as well.
Infinispan - folks from JBoss have created this one
EHCache - a popular distributed cache
Hope this helps