Probably not.
Ghosts do not have a physical body: they are merely spiritual shades of what used to be people. Their corpse can be treated in the same way as any other, and the physical bodies of most of the ghosts we encounter in the series must have decayed long ago. So it seems that the visible form taken by a ghost is what their body looked like at the moment of death: hence Nearly Headless Nick looks as he did just after he was executed, not the mouldering skeleton he physically became afterwards. For the same reason, ghosts retain the clothes they were wearing when they died: hence Nearly Headless Nick never changed out of his Elizabethan ruff into something more appropriate to this day and age.
Given this assumption, it's clear that his ghostly appearance can never change: he'll always be nearly headless.
This doesn't contradict DVK's answer here, since the games he mentions involve ghostly interaction but not any change in the 'bodies' of the ghosts involved, since their heads are already detached.
As Richard pointed out in a comment, it also stands to reason that Nearly Headless Nick would have got himself properly beheaded if he could. He spent several hundred years hanging out in a whole building full of witches and wizards, including some of the greatest of their age such as Dumbledore. If they couldn't tell him how to get his head entirely removed, nobody could; and if they could, he would presumably have done it, since nearly headlessness is his main grievance in life death.
As for your bonus question (which admittedly is now hypothetical only), consider the completely headless ghosts, such as those involved in the Headless Hunt. They get on perfectly well in
life death with their heads detached from their bodies, and
neither head nor body goes to waste; both remain part of the ghost, able to move and communicate.