Despite the wide use of wide angle lenses (sorry no pun intended) for landscape photography, they are not the only viable solution for landscape photography. I highly recommend trying out a telephoto lens for landscape shots like this. With a wide angle, you bring in everything, both foreground, bright sky, and everything inbetween. A lot of times, these extra elements are just undesirable and add clutter and noise that detracts from the overall image you are trying to create.
With a telephoto lens, you can reach past the foreground, and under the sky, and capture the key parts of the landscape. You have more power to bring out finer details, nuances of shadow and light, in just the mountains. You will have the ability to reduce the amount of sky in the shot, which can help you resolve those high contrast differential problems. If you still want to capture the full breadth of the mountain range, you can take a panoramic set with a telephoto, and stitch them together after the fact.
A telephoto lens with a lens hood can also improve contrast a bit in the face of haze. Part of the problem with haze is the contrast-reducing effect it has is due to the dispersal of light. A wide angle lens will pick up light from a high number of angles, enhancing the effect of haze. A telephoto lens will only capture light that comes more or less strait into the lens. Combined with a lens hood, a telephoto lens should help you cut through some of that off-axis dispersed light and capture a bit clearer shot. (This effect is not huge, but sometimes it can help produce a clearer shot.)
If you still have issues with contrast, a Graduated ND (neutral density) filter or set of GND filters can be used to reduce the brightness of the sky, and lowering the dynamic range of the scene. Combine some GND filters with a telephoto lens, and you should be able to capture some great shots of that mountain, despite its distance.