If you want to get really bummed out for 'what could have been', check out the Wikipedia page for List of manned Mars mission plans.
The earliest plan to get to Mars was written by von Braun in 1948, with the idea that we would be landing in 1965. With our current knowledge of Mars, it reads like science fiction. Seven passenger ships and three cargo ships would be assembled in Earth orbit using reusable shuttles to launch the materials. They would fly to Mars in the same way we do currently, at the optimal transfer window. They would find a landing site from orbit. A manned glider would be used to make the first landing on Mars, using skis to land on the polar ice cap. The crew would then travel overland using rovers and then build a landing strip.
http://www.astronautix.com/v/vonbraunmarpedition-1952.html
Obviously we now know much of this would be impossible. Mars doesn't have the thickness of atmosphere needed to support landing with gliders, and the radiation of interstellar space was completely unknown at the time. Additionally, the technology and engineering which would be needed to develop reusable shuttles were almost 30 years away, and even then NASA was unable to keep reuse tempos anywhere near what would be necessary for an extended space construction project.
Quick budgetary baseline here: Apollo cost about $107 billion in today's dollars. Here are the yearly figures in that-year-dollars from Wikipedia:
The NASA estimates for the space shuttle (which was being costed and developed around the same time Von Braun and Boeing were putting together) was 43 billion in 2011 dollars. This was based on 50 launches per year, which was very unrealistic (lots more to be said here, effectively NASA planned for the Space Shuttle as being the sole launch vehicle for the entirety of the US including commercial and military launches). The actual final total for the space shuttle was 196 billion, so the estimates were way off.
Back to the plans. Von Braun updated his plan throughout the Apollo program, and at the very end of his career, proposed his 1969 plan. This plan was huge, and would likely have required an amount of investment in excess of what Apollo ran (his estimate was a peak of $8 billion per year, which is more than double what Apollo cost at its peak). The first step of the plan was the space shuttle, albeit a far different shuttle than the one you and I know, mainly because it would use a nuclear rocket for propulsion. This would be followed by an earth space station, and finally the creation of the spacecraft which would take us to Mars. The main lifting vehicle from Earth for this would be a future-state Saturn V, the Saturn V -25U. This rocket would be a longer version of the Saturn V which took us to the moon, with four solid rocket boosters attached to the bottom, and the upper stages replaced by NERVA, a nuclear rocket engine. This rocket was entirely technically possible at the time, and would have required significant but not impossible engineering and integration work.
http://www.astronautix.com/v/vonbraunmarpedition-1969.html
The two Mars ships would be assembled in Earth orbit, fly to Mars using a standard trajectory, astronauts would descend using a to-be-designed descent module, stay for 90 days, then swing by Venus on their way back to Earth, docking with the space station and then returning in the reusable shuttle.
The big driver for the 1969 plan, as well as for a competing plan from Boeing, was the NERVA rocket. Nuclear Engine for Rocket Vehicle Application (NERVA) was a nuclear-based rocket engine.
https://en.wikipedia.org/wiki/NERVA#/media/File:NERVA.jpg
This rocket engine was (and may still eventually be) the key to interplanetary travel. In a nuclear rocket, you don't need a chemical fuel. Liquid hydrogen is used, and is heated to a very high temperature in a nuclear reactor. As in a conventional rocket engine, the gas then expands and is propelled out the back of the ship. NERVA would have provided basically twice the fuel efficiency of a chemical rocket. I keep saying 'would have', but NERVA was an extensively developed project. Research on nuclear thermal rockets began in 1952, and continued for two decades. Two engines were built and tested. The second, NERVA XE, was basically a complete flight system and tested in a near-vacuum environment. It ran for a total of 115 minutes and was started 28 separate times.
In my opinion (and the opinion of 1960s engineers far far smarter than I), the answer to whether we could have done it technically is yes. The budget would have needed to exceed that of peak apollo, but that would have included far more than just the Mars mission, but also an earth-orbit space station, a reusable shuttle, and a nuclear rocket engine. Whether those estimates were reasonable, given the massive expansion of the space shuttle compared to initial estimates, is debatable. Whether it would have survived the political pressures not only to cut spending in the 70s and 80s, but also the environmental movement which was (and is) diametrically opposed to nuclear rockets is another. But if we'd been willing to double the investment we were making in Apollo, and public support had existed, I absolutely think we could have gotten not only there but to even more distant parts of our solar system.