I want to change the icon in the start menu:
I'm willing to mess with the Registry, and I am well aware that I should make backups (and do!)
How will I accomplish this?
Unfortunately Microsoft has since patched the icon registry key. Gone are the good old easy replacement.
If you are unwilling to install 3rd Party software, then there is no current solution to your problem.
Some third party software that will achieve your goal
There may be other software available, but these are the current ones I know of. I do not want to turn this into a software recommendation, but this provides an answer to people who come here looking for a solution.