Sachverhalt: A. In den Betreibungen Nr. xxx und yyy des Betreibungsamts Q._ gegen X.Z._ deponierte der Weibel die Zahlungsbefehle am 24. November 2012 im Briefkasten der Familie Z._, Liegenschaft I._, in J._. B. Am 4. Dezember 2012 verlangte X.Z._ vom Bezirksgericht Hinwil als unterer kantonaler Aufsichtsbehörde die Aufhebung der beiden Betreibungen, die Feststellung, dass sein Betreibungsort K._ sei, und die Anweisung an das Betreibungsamt, seine Adresse Dritten nicht bekannt zu geben. Das Bezirksgericht holte Vernehmlassungen vom Betreibungsamt Q._ (Vernehmlassung vom 20. Dezember 2012) und von den Gläubigern (Beschwerdeantwort vom 21. Dezember 2012) ein. Das Bezirksgericht versandte diese Eingaben an X.Z._ mit Einschreiben vom 31. Dezember 2012, wobei es im Begleitbrief darauf hinwies, dass ihm die Unterlagen zur Kenntnisnahme und zu seinen Akten zugestellt würden. Diese Sendung wurde am 3. Januar 2013 ins Postfach avisiert und am 10. Januar 2013 abgeholt. Bereits mit Urteil vom 8. Januar 2013 wies das Bezirksgericht die Beschwerde ab, soweit es darauf eintrat, und auferlegte X.Z._ die Gerichtskosten von Fr. 300.-- wegen Mutwilligkeit. C. Gegen dieses Urteil erhob X.Z._ am 1. Februar 2013 Beschwerde an das Obergericht des Kantons Zürich als obere kantonale Aufsichtsbehörde. Er verlangte die Aufhebung des angefochtenen Urteils und der Betreibungen, den Verzicht auf die Kostenauflage und eventuell die Rückweisung an die Vorinstanz. Mit Urteil vom 4. April 2013 wies das Obergericht die Beschwerde ab. D. Am 22. April 2013 hat X.Z._ (Beschwerdeführer) Beschwerde in Zivilsachen und subsidiäre Verfassungsbeschwerde an das Bundesgericht erhoben. Sinngemäss verlangt er die Aufhebung des obergerichtlichen Urteils. Die beiden Betreibungen seien aufzuheben. Eventuell sei die Sache an die Vorinstanzen zurückzuweisen. Zudem ersucht er um aufschiebende Wirkung und ferner - für den Fall des Ungenügens seiner Beschwerde - um unentgeltliche Rechtspflege und Verbeiständung. Schliesslich verlangt er eine Entschädigung für die Beschwerdeführung vor Bundesgericht. Die Gläubiger (Beschwerdegegner), das Obergericht und das Betreibungsamt haben sich dem Gesuch um aufschiebende Wirkung nicht widersetzt. Mit Präsidialverfügung vom 8. Mai 2013 ist der Beschwerde aufschiebende Wirkung zuerkannt worden. In der Sache haben die Beschwerdegegner und das Obergericht auf Stellungnahme verzichtet und das Betreibungsamt hat sich nicht vernehmen lassen. Am 25. Juni 2013 reichte der Beschwerdeführer eine weitere Eingabe ein, mit der er verlangt, das Betreibungsamt anzuweisen, die beiden Betreibungen bis zum Entscheid des Bundesgerichts aus dem Betreibungsregister zu löschen und ihm einen Betreibungsregisterauszug ohne die beiden Betreibungen auszustellen.