The limitations one worked with and the techniques for getting around those limitations (when that was possible at all) differed considerably depending on the scene you were trying to capture as well as on the film you were using.
Graduated and split neutral density filters were part of the game, certainly, but they were only the beginning. But understand that that "beginning" could extend, in the case of a landscape photographer using a large-format (8x10 or larger) camera and colour transparency film, all the way to creating a custom cut-out ND gel (created by tracing the image on the camera's ground glass), which would be stuck to a plate and used in a compendium lens shade (sometimes called a "matte box") in front of the lens. Mind you, those were the obsessive types who created images for the calendar, jigsaw puzzle and coffee table book markets — they tend to make a dozen or two spectacular pictures each year by showing up at the same location for weeks on end, waiting for everything to be exactly right, and going home without taking a picture more often than not.
In the very beginning, there was image composition — something we of the Photoshop generation tend to take for granted, and tend to assume is a new thing. (If we understand that it was done in the past, we tend to think of it as special-effects trickery, or in terms of surreal images like those created by Jerry Uelsmann.) The fact of the matter is that it as almost necessary in the early days, since the plates or paper negatives were sensitive only to blue light. Because exposure for things other than the sky depended on capturing whatever minuscule amounts of blue light were reflected by non-blue things, one couldn't actually create an image that had both sky and ground detail. If the plate had a sensitivity that was equivalent, say, to ISO 1 for things terrestrial, it also had a sensitivity equivalent to ISO 64 for the daylight sky, which would put the sky somewhere around 8 stops brighter than the midtones of the landscape at the best of times. So you had a choice: white skies, or separate exposures. (And if you're going to do separate exposures, why not just have a stock library of pretty and dramatic skies on hand, eh?)
Orthochromatic film (sensitive to violet, blue, green and into the yellows) lessened, but did not solve, the sky problem. When panchromatic B&W film (sensitive across the visual spectrum) came along, the nature of the problem changed completely. One no longer had to accept losing the sky altogether as "just thee way things are" since it became possible to capture the sky and the ground in the same exposure. And that, more than anything else, put the notion of image compositing on the back-burner in most minds.
With B&W pan film, your choices are almost unlimited. If the too-bright areas of your image can be isolated by colour (like a blue sky), then you can use one of the band-block filters to selectively tone down that portion of the spectrum. That's why people used filters like the K2, #25 and #29 filters — they all block short-wavelength (blue & violet) light to varying degrees, which could provide anything from a detailed-but-plausible sky to something really dramatic. (The K2 could almost be considered a contrast-correction filter.) You could also use a split or graduated neutral density filter (or a split colour filter, depending on the effect you wanted to achieve).
The biggest tool in the arsenal, though, was contrast manipulation in development. Developing for a shorter period of time results in a thin, low-contrast negative, and developing longer results in a dense, high-contrast negative. With a "proper" exposure, either will ruin the picture. But if you deliberately overexpose the negative and then under-develop, you end up with a negative that has normal density and lower-than-normal contrast. (Similarly, if you under-expose and over-develop, you get a normal-density negative with very high contrast.) With this knowledge in hand, you can quickly get to a rule of thumb that says: expose for the shadows and develop for the highlights. That requires metering, usually with a spot meter (not incident metering) to assess the absolute values of the shadows and the relative values of the highlights.
The Zone System is a way to systematize that process. Through testing, one can develop sets of exposure/development combinations for various films that will accommodate various contrast ranges such that they can be printed on a standard paper. The "real" Zone Sytem is an image-by-image thing, and is really only suitable for sheet film (or rolls that are shot entirely under on set of conditions); the "standard operating procedure" for roll-film shooters was to find a good N-1 recipe and rely on paper contrast grade changes to make up the difference between negatives.
As with HDR, though, that results in a job half done. It's really nice that you managed to get everything into one image, but the result is flat and uninteresting until it is tone-mapped. (And it really is; see Chip Forelli's B&H Event Space presentation Straight Print to Finished Print: the Untold Story for a lot more info.) That's where dodging and burning come in — one needs to put back all of the interesting details that creating a low-contrast image minimized. That, of course, is a lot of work — work you can lessen quite a bit by combining the Zone System with selective colour filtration and graduated/split ND filters at capture time.
Colour film changed the game again. Not only does it have (mostly) inherently lower latitude than panchromatic B&W, it is also much more prone to reciprocity failure. This isn't the simple reciprocity failure of B&W film, where you need to make long exposures even longer. Anyone can cope with that, and long exposures with colour film are not much more complicated than with B&W film. No, there's a complex interplay between the silver and colour developers, along with the differing depths and thicknesses of the colour emulsions, that mean that there is only a small range of development times where the relationships between the various colours is even close to workable. For slide films, a one-stop push or pull is drastic and already starting to show colour shifts. For colour negatives, you start running into unfixable colour shifts at about 1 1/3 stops over and 1 2/3 stops under (depending on the film; "consumer" Kodaks were better-behaved but had strikes against them in other areas). And even when you could get the contrast right, pushing and pulling would do things to saturation that might not fit the image.
So how did we handle contrast with colour? Well, we started by choosing the right film for the job. A wedding photographer, for instance, would gravitate towards something like Kodak's Vericolor III Professional (VPS), which had a wide latitude and low saturation, and could (if used carefully) capture both the bride's dress and the groom's tux comfortably and render good skin tones. But VPS would result in a pretty bland landscape. So we used films with a bit more saturation and "punch", often picking different films for different circumstances (you couldn't top Kodachrome for fall foliage, but Fuji's Velvia had it beat six ways from Sunday for lush spring vegetation). We used split/graduated ND filters where they made sense. Since printing upped the contrast again (especially for Cibachromes/Ilfochromes made from transparencies) we'd use contrast masking to knock it back down again when it was appropriate. And — perhaps most importantly — we learned to make strategic sacrifices when they made sense. If blacks had to block up or whites had to blow out to make the best picture, that's what we did. It wasn't a tragedy in those days. (I'm not convinced it's a tragedy today either.)