Какое key-value хранилище лучше?

Нет лучшего NoSQL хранилища вообще, есть под задачи, у каждого плюсы и ограничения. Redis супербыстр когда оперативки больше чем данных, иначе он часто подгружает с диска и сводит на нет скорость (если это еще не переделали), хорош для очередей сообщений, списков (встроены сортировки), всякой мелкой инфы. memcache (не memcached) самый быстрый но не флашит на диск ничего (собсвенно оттого и). memcached простейший key-value с флашем (хорош для очередей сообщений и всяких счетчиков). У последних двух особенность multiget — взять много ключей за раз работает столько же сколько и один, так что хорош для хранения «превьюшек» данных по их id, когда сортированные списки хранятся где-то еще (в редис). MongoDB не просто key-value, в ней можно хранить целые документы (пост со всеми комментариями), некий компромисс между nosql и RDBMS. Hbase уже совсем замена RDBMS, один из самых быстрых когда речь идет о IO диска, соответственно эта NoSQL для постоянного хранения стопитцот миллиардов данных. Cassandra похоже конкурент Hbase, но аутсайдер, т.к. фейсбук/твиттер от нее отказываются ;) Про CouchDB и Riak я ничего особенного не слышал (может кто дополнит — мне интересно)

Ходят слухи, что Redis очень даже неплох. Как минимум для сессий.

Сессии — SessionStorage;
Данные — LocalStorage;
Конечно разумно если есть специфические отличия в типах хранящихся данных.

Kyoto Cabinet, позволяет делать порядка 1 миллона операций записей в секунду, операций чтения ещё больше.

1) Redis
2) Redis или MongoDB
что тут обосновывать — каждый кулик своё болото хвалит, всё субъективно :)

Про BrekeleyDB (в том числе Java edition) почему никто не упоминает?

Стоит ли использовать два различных key-value хранилища в одном проекте под разные типы данных?

Обязательно, если под типом данных имеется в виду не картинки vs текст :) а время жизни данных, их количество, их актуальность, необходимость сортировок, фильтрации, поиска и т.п. Вон для кроме MySQL + Sphinx вроде и нет ничего лучше (готового).
И вообще, NOSQL — not only SQL, что намекает ;)

Если Вас не беспокоит вендор лок — порекомендовал бы google datastore.

Посмотрите в сторону LevelDB, он имеет высокую производительность, но не имеет собственно сервера. Встраивается напрямую в приложение.

Вопрос в догонку :)
А как насчет выбора хранилища для сессий в режиме мастер-мастер, расположенных в разных европейских странах? MongoDB не справлялся.

посмотрите также Tokyo Cabinet как альтернативу memcache.

На самом деле 2 реальных альтернативы:
1. Когда данные помещаются в память: Redis (мемкэш — вчерашний день, уступает по функциональности)
2. Когда не помещаются: обертка над handlersocket (у него нет автоматического expire, но если данные на диске, оно не нужно). Обертка, потому что в mysql 5.6 возможно будут лучше варианты.

Все остальное — либо экзотика, либо медленное, либо вообще из другой оперы.