Greetings,
Saw your post and thought I'd try to help you find a clue or two. I recognized the Coleman name from my research and while I do not have any direct info on your Nathaniel I might have some info that could help you along the way.
I run a web site for descendants of the Fish Brothers of Sandwich and we share gedcoms and post our research on our website. I checked there and we have 40 Coleman's from Sandwich or Barnstable born both before and after your Nathaniel. One of more of those may lead you to him.
We also have a forum there so if you'd like feel free to register and post under the "other names" section. We may have a member that can help you more.
Also..have you found the book titled "The History of Cape Cod: the annals of the 13 towns of Barnstable County" by Fredrick Freeman? Its available free in pdf at books.goggle.com You may want to try looking thru it. Since the Barnstable county courthouse burned to the ground with most of its records I think in the early 1900's much info is lacking via town records but thankfully books like this are out there.
good luck in your search
Our web site is
www.allaboutnhre.com/fishsandwich