What's the absolute earliest anyone could reach the moon and back with a crewed mission with a POD after Gagarin? It can be a mega risky mission, just has to be theoretically possible.
Maybe Lunar Gemini in the mid-sixties?
I'm going to answer primarily for the American side. The TLDR is:
Flyby: Late 1965 for a flyby, using circumlunar Gemini (limiting factor being flight proven Gemini, but having the Saturn IB instead of the Saturn I avilable is a nice bonus to mission margin)
Landing: More complicated. Mid to late 1967, maybe even mid 1968.
Any profile using Saturn V or another new-build launcher is unlikely to happen much before late 1968, maybe early 1969. Apollo 8 already launched on only the third launch of the Saturn V, and after a very contentious debate about putting men aboard (the previous flight, AS-502, had some really eyebrow-raising issues which they worked out, but Apollo 8/AS-503 was the first
proof that they had solved them--some people wanted one more unmanned launch).
If you avoid Saturn V, your next pacing item is driven less by capsule availability (Apollo isn't going to be ready until early 1967 even if you fix the gas issues during development and short-circuit the Apollo 1 fire) and more by the requirement to use docking to assemble a trans-lunar stack from multiple launches of something like Saturn IB or Titan IIIC. You need about 80-90 tons even if you skimp on the capsule by going with Gemini and use a one-man lander and a need to use non-cryo propellants like hypergols so they don't boil off in the time it takes to launch and dock that many Saturn I payloads may drive up that minimum number due to lower performance than hydrolox propellants. You may be looking at more like 6-7 launches of Saturn IB. Whether you dock together multiple TLI stages launched separately to make up the mass or launch the stage empty and then fill it from tankers, you still need reliable docking on about 8 occasions in this mission profile. If you're unlucky, you're stuck with manned docking, which knocks a Gemini capsule's mass off every tanker/assembly flight, but doing unmanned docking stumped the Russians until 1969 and isn't likely to come tremendously easily to the US before 1968/69. It'd look something like the mission plans I used in Dawn of the Dragon.
Gemini demonstrated docking in orbit on Gemini 8 in March '66, but they didn't manage it a second time until Gemini 9 in July '66 due to issues with the docking system on the target vehicle on Gemini 9 in June '66. Thus, I'd say any mission depending heavily on docking needs to wait for its first test flights until fall 1966. With test flights of the assembly sequence or fueling technologies first, you're looking at maybe late spring or summer of '67 at the earliest for first landing stack through translunar injection, which can either land (risky) or do an Apollo 10-style near-landing demo with a subsequent landing in mid-to-late summer of '67.
You'll need every Saturn pad you can get--LC-34 has one, there's two at LC-37 if you finish both instead of just the one of OTL, and then two or three at LC-39. If you're lucky, you can get 6 Saturns off in only a few days, but the launch and docking campaigns are likely to stretch to closer to a week, maybe even three considering you need 6 perfectly trouble-free launches to a very specific orbit (which will need launch windows about as tight as ISS missions today).
The lander itself is another question, since it too is likely not ready until 1967 or late '68. Even with a Gemini-based lander, you have substantial development work to do on the landing and ascent systems. I'm not sure anyone could have bettered Grumman's schedules--they were incredibly tight. It wouldn't surprise me if the lander ends up being the pacing item, driving things more towards late '67 or '68 (if this is the only new spacecraft, there may be some more ability to accelerate, but not much.) Hence, the TLDR: 1967 really generously, probably more like 1968.
It requires the following:
-Accept a radically limited system, landing only one crew member per flight and using the very small Gemini cabin for the capsule and possible as the lander cabin.
-Push the lander schedule to the breaking point
-Use multiple launches of Saturn IB instead of Saturn V, and solve the issues with docking several transfer stages or transferring propellant from tankers this will require. May require use of hypergols, driving initial mass in LEO to the 100-110 ton mark in spite of the lighter capsule and lander and requiring 5-6 launches if you can dock unmanned on automatic controls. With manned docking controlled by Gemini, you may even need more like 7-8 launches to assemble the mission, and at least a month or so to get everything for a mission launched, onto their respective pads
-Every Saturn pad you can get. Build both pads at LC-37, build three or maybe even four pads at LC-39, find out if you can squeeze in a second pad at LC-34.
-Order Saturn IB in bulk. You'll need them by the dozen. Get McDonnell to build you a cheaper S-IVB and IBM to chop cost out of the Instrument Unit (the two biggest cost centers on the Saturn IB).
http://www.svengrahn.pp.se/histind/Ugol/Ugol.html