Question: Is there a way to send a 'form' to your Contacts (not registered as Users), get their reply and update their respective contact record based on the replies. 
Has anyone done this before?
Till now I have, 
1) create a **public site** with
2) a **visualforce page** accessing a **visual workflow** screen as form which 
3) updates the contact record
3) Send site URL through **email** manually.

Thank you

Answer: 
Your approach is fine, but site guest user does not have update permission on contact, so your flow will need to write to a custom object and you can use process builder or autolaunched flow to update contact record.

I wrote up a post around using flows as a replacement for stay in touch that is similar to what you are doing

<http://goravseth.com/replacement-for-stay-in-touch-using-flows>

Note that I do not know if this approach violates Salesforce terms of use, since it bypasses the restriction on site guest user updating contact, so keep that in mind.
According to me the best way is -

1. Create a visualforce page as form.
2. Host that page on your public site.
3. Create a button on the contact detail page that will shoot the email for that particular record.
4. You should have an email template pointing to that public site url and should have the contact id or any unique id that will identify the contact to which the response will be recorded.
5. The #3 and #4 will be linked thru an another visualforce page which will be responsible to shoot email (the controller of this visualforce page will select the email template that you created in #4).