I asked my local SSL expert, and he mentioned: the list the client sends is just a preference list; the server can choose what it wants.
For example, nginx by default[1] specifies an OpenSSL cipher list of HIGH:!aNULL:!MD5, which you can examine by running
$ openssl ciphers 'HIGH:!aNULL:!MD5'
You'll see neither RC4 nor MD5 in that list. (You will if you run a plain "openssl ciphers", so you can see openssl knows about them but the config turns them off.)
(I'm an SSL newbie, please correct any mistakes I've made in the above.)
You are right, the final choice of the algorithm is with the server. I am not sure though if it is possible to give other ciphers a higher priority on the server without completely disabling RC4 (which is still better than no encryption / no connection).
For example, nginx by default[1] specifies an OpenSSL cipher list of HIGH:!aNULL:!MD5, which you can examine by running
$ openssl ciphers 'HIGH:!aNULL:!MD5'
You'll see neither RC4 nor MD5 in that list. (You will if you run a plain "openssl ciphers", so you can see openssl knows about them but the config turns them off.)
(I'm an SSL newbie, please correct any mistakes I've made in the above.)
[1] http://wiki.nginx.org/HttpSslModule#ssl_ciphers