Как вариант, моно сделать это с помощью апплета. Но я никак не соображу, как запросить сертификат пользователя. Возможно ли это сделать не устанавливая на машину пользователя JCP?

Т.е. вариант с апплетом, как я понимаю, ничуть не лучше CAPICOM?
PS: Примера с апплетом не нашел в samples.

Примеры с апплетом не вошли в последнюю сборку.
Если вы хотите подписывать на клиенте, то необходимо иметь хранилище ключевых контейнеров, а следовательно и установленный провайдер. Т.е. вам необходимо написать апплет, который бы имел диалог выбора ключа на клиетской машине, подписывал необходимые данные и отправлял на сервер (на клиенте должен быть установлен JCP).