After a lot of search, the solution turned out to be easy. The key is to disable cipher suites that use DH keys. I managed to do that using the following commands:
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_RSA_WITH_AES_128_CBC_SHAAfter that, Webmail worked again. You can check supported ciphersuites using sslscan command, i.e. in my case after the given change I got the following ciphersuites:
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_RSA_WITH_AES_256_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_RSA_WITH_3DES_EDE_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_RSA_WITH_DES_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_RSA_WITH_DES_CBC3_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_EDH_RSA_WITH_3DES_EDE_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites SSL_EDH_RSA_WITH_3DES_EDE_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_DSS_WITH_AES_128_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites TLS_DHE_DSS_WITH_AES_256_CBC_SHA
zmprov mcf +zimbraSSLExcludeCipherSuites SSL_DHE_DSS_WITH_3DES_EDE_CBC_SHA
zmmailboxdctl restart
$ sslscan webmail:443 | grep AcceptedEven though Webmail worked, Thunderbird didn't connect. Using Wireshark I found out that Thunderbird, for IMAP connection, tries to use EDH-RSA-DES-CBC3-SHA. I tried to disable that ciphersuite on the server side, but no matter what I've tried, it didn't work. In the end I disabled that cipher on the client side. I opened Thunderbird's configuration editor and there I manually disabled given cipher by setting configuration setting to false.
Accepted SSLv3 256 bits AES256-SHA
Accepted SSLv3 168 bits EDH-RSA-DES-CBC3-SHA
Accepted SSLv3 168 bits DES-CBC3-SHA
Accepted SSLv3 128 bits AES128-SHA
Accepted SSLv3 128 bits RC4-SHA
Accepted SSLv3 128 bits RC4-MD5
Accepted TLSv1 256 bits AES256-SHA
Accepted TLSv1 168 bits EDH-RSA-DES-CBC3-SHA
Accepted TLSv1 168 bits DES-CBC3-SHA
Accepted TLSv1 128 bits AES128-SHA
Accepted TLSv1 128 bits RC4-SHA
Accepted TLSv1 128 bits RC4-MD5