Solver-o-matic
Decision Tree for Nonsmooth Optimization Software
Your first choice should be Limited Memory Bundle Method (LMBM) (you need to code difference approximations by yourself). LMBM is specifically developed for large-scale nonsmooth optimization by N. Karmitsa. It works best for highly nonlinear functions. The Fortran 77 source code and the mex-driver (for MatLab users) are available.
Not satisfied?