In regenerative cooling the fuel is passed around the nozzle before being pumped into the combustion chamber right? I don't really see how this affects cooling itself, since the heat captured around the nozzle by the fuel/oxidizer seems to be pumped back into the combustion chamber which will have to be captured back by more fuel. So where is my reasoning wrong?
You are missing how heat is distributed in exhaust.
Most of propellant ejected through the nozzle never makes contact with the nozzle surface or walls of the combustion chamber, and as result never has any chance to transfer its heat into them.
The exhaust gas primarily cools through adiabatic expansion - high pressure and high temperature both transformed into rapidly increasing volume and velocity of the ejected propellant - high-speed ejection of reaction mass; propulsion. Only a minor part of it is transferred into the walls - but that is still enough to risk damage to them through overheating and compromising durability of the materials.
On the other hand, some of the combustion energy is consumed on heating the fuels from their injection temperature to post-combustion temperature (which then transforms into propulsion). The hotter the fuel before injection the less is lost to that heating. So it's beneficial to heat the fuels - especially to boil off cryofuels - before combustion.
Since we both have some excess heat we need to get rid of, as it's dangerous to the structure, and we need the cryofuels turned from liquid to gas for combustion - we can combine the two processes, simultaneously increase the pre-combustion temperature and cool the structure. Most of the heat produced in combustion will be ejected "harmlessly" - and what excess does transfer to the structure, gets recuperated and reused by pre-heating the fuel, that energy which would be otherwise lost, pumped back into the combustion chamber as hot fuel.