Clearly, the Saturn V is going to be retired. There's just no way around that, and production was already being shut down by 1968. That means that what we're looking for is basically a rocket to replace the Saturn IB; medium-lift, man-rated, low operations and purchase cost would be key characteristics. To my mind, that gives a couple of possibilities:
First, we could have another Saturn family rocket. The Saturn IB as is might work, except that it was expensive (Astronautix cites ~$100 million/launch in 1965 dollars!) and shared relatively little of its design with the Saturn V. The Saturn II designs using an S-II as the first stage and an S-IVB second stage have a certain appeal, except that they require SRBs for any reasonable payload, use hydrolox for first stage propulsion[1], and use the J-2--designed for upper-stage applications--as a sea-level engine. The J-2's a good motor, but that just isn't going to work well. A third possibility would be an "all-solid" Saturn, analogous to the Ares I. This was seriously considered with several different possible configurations. However, like the Ares I, such a design is going to have a number of problems that will likely render it untenable. Finally, you could build a new design utilizing Saturn components like the F-1 and J-2 (ie., the Saturn II from my TL). This, however, would impose a certain development cost, though if designed properly it might be able to reuse much existing equipment. In the end, the difficulty with all Saturn-based designs is that they will be quite expensive and have the main advantage of sharing a great deal of parts commonality with a booster that won't even fly anymore. It is hard to see why production would be continued, aside from certain political considerations and NIH syndrome.
Second, you have the other major man-rated medium-lift launcher of the era, the Titan. There were two major versions of the Titan, the ones without SRBs (all the Titan IIs and certain versions of the Titan III; for simplicity, I will refer to them just as Titan II, and you may take it for granted that this also includes the Titan IIIB etc.) and the ones with (most of the Titan IIIs). The Titan II would be grossly inadequate for lifting Apollo or even, most likely, Big Gemini, so it may be ignored for our purposes. The Titan III had a number of advantages compared to the Saturn IB, particularly in being much, much cheaper to launch without sacrificing very much payload. There were even a variety of possible upgrades (stretched SRBs, large-diameter core, cryogenic upper stages) that would have erased that payload gap without impacting the cost much. It could even have commonality with Saturn, if that was desired, for example by using the J-2 as a cryogenic upper stage engine. It's even possible that you could build an ersatz HLV through certain modifications, such as combining multiple core stages (ala EELVs). The major difficulties here are political and access considerations, and the highly toxic (and hypergolic!) fuels the Titan uses. As the Titan was primarily an Air Force booster, it is possible that that agency will object to some production being diverted to NASA, or that NASA will suffer NIH syndrome over use. Consolidating production like that may also cost one or both groups support on the Hill. However, the cost advantages are very significant, which may be an even bigger driver.
There aren't really any other choices. Soviet rockets are obviously not going to fly, Europe hasn't built anything even remotely capable of handling Apollo yet, and aside from Titan and Saturn, the US has a lot of rather smallish rockets, Atlases and Deltas and such, not the sort of thing needed for this type of mission.
EDIT: [1]: Hydrolox is inferior for lower stages despite its generally higher performance because it requires a bulkier (and therefore heavier) tank structure. This often outweighs the weight savings from switching to hydrolox (from kerolox) in the first place. It also means the rocket will be less aerodynamically efficient, another problem. Finally, it's just plain harder to build really big hydrolox engines compared to kerolox, if the RD-170 and F-1 are any indication.