I can't quite remember all the details, but I have successfully done this.
First connect the iPod to your PC and open iTunes.
In the left hand column, devices are listed with the name.
If you highlight and overtype the new name I think that is all you need.
Or it might be a right click and rename. It is this last stage that I can't remember, but I know it was much easier to do than I expected.