I have a 4 months notice period. I would like to leave much sooner. I never negotiated a reduction in the notice period: should I do it before or after resigning? Can I give HR the full 4 months and then get it updated? I don't want HR to stall my resignation.
You should do it when you resign - not before ("hey, I'm going to resign, but before I do can we change my notice period") or after - but be prepared to be stuck with the full period.
Simply state in your resignation letter that you recognise that the full notice period requires you to work to "x" date, but that you would like to negotiate a shortened period, if possible. What happens next depends pretty much on your current role, the situation regarding projects and such, and the personality of your manager(s). Whatever the response is, you're stuck with it and it won't be worth fighting a negative response.
If this is because you have another position lined up, but need to provide a start date, negotiate a start date that accounts for your full notice period with an option to start sooner. That way, you won't get caught short if the new job evaporates before your notice period ends, or your notice period is reduced but then you have a gap before your new job.