He had been here for around 12-16 years. His head may have been stored to prevent the degradation associated with staying in one shape.
We learn in "The Box" (Season 3, Episode 2) that Newton has been in our universe for around 12 to 16 years, because he tells Fauxlivia that he has been here since she was in high school, and she is roughly 30 at the time of the episode.
As for how his head was lost, there seems to be no information on this. None of the creative personnel have established a backstory for Newton other than the few tidbits we hear in screen.
However, we do know that shapeshifters cannot stay for too long in one shape, as Newton had explained that Faux-Charlie's degradation was the result of precisely this.
Furthermore, Newton is never seen to change shape — even when it would be advantageous for him to do so — despite being a mercury-based mechano-organic unit like the other shapeshifters.
Since Newton is the leader of the shapeshifters, it stands to reason that he may have been the first (successful) one constructed by William Bell for Walternate. As a result, he may operate differently than the newer models sent more than a decade later. For instance, he may not be able to change shape in mere minutes using a device (e.g. the one with the three-pronged cables) like the newer shapeshifters can. Alternatively, he may be unable to change shape at all: while possessing the mercury-based technology required to survive the transition between universes, the ability to change shape may be purely a newer tech implemented by Bell.
In either case, the inability to stay in one shape for too long combined with an inability to shift (or shift easily) may mean that his head was purposely removed and stored in order to halt an eventual degradation until he was needed.
As William Bell was the only person who knew which facility was storing the head, it stands to reason that Bell was the one who had it removed and stored.
What is unclear is why Bell did not tell Walternate the location of the head when they needed it, given that Bell was trying to maintain Walternate's trust. It is possible that, in trying to protect our universe, he fabricated a reason as to why he does not know the location. (He may have told Walternate that he didn't apprise himself of the exact facility in order to minimize the chances of the information falling into the wrong hands.)