Unfortunately, I don't have specific info regarding Matthaeus' parents (I'm also searching for that info).But I do have the following information regarding his Hessian service (you might already have this info---- but for those that don't, it might help in the search for the parents.) ----
HETRINA III #10657 lists Matthaeus Noeding, born 1754/55 Berheim D3509. A soldier in the Hesse-Kassel Regt. Rall, 3. Comp. Listed as a deserter in June 1779. This soldier is NOT on the Trenton prisoner list. There is also another soldier from the same Regiment and Company named Nikolaus Noeding, born 1754/55 at Schnellrode D3509, who was captured at Trenton, N.J. on 26 December 1776 and still listed as a prisoner in 1783. Both villages Bergheim and Schnellrode are close together near the town of Spangeberg/Hessen. In addition, there was one soldier of the Kassel Regt. V. Wissenbach-- Noeding, Justus..also from Bergheim, who died in July 1780 of sickness or accident, possibly a brother or cousin of Matthaeus.
I'm happy to share any Nading info that I have. Let's hope one of us gets lucky in this quest!