Sachverhalt: A. Die Staatsanwaltschaft IV des Kantons Zürich führt gegen A._ eine Strafuntersuchung wegen sexuellen Handlungen mit Kindern und weiteren Delikten. Konkret wird A._ vorgeworfen, am 19. Juli 2016 um ca. 16.15 Uhr an drei unter 9-jährige Mädchen herangetreten zu sein und eines der Mädchen, B._, gefragt zu haben, ob es sein Geschlechtsteil anfassen wolle. Zugleich habe er sein Geschlechtsteil vor ihren Augen entblösst und daran manipuliert. Nachdem B._ seine Frage bejaht habe, habe er B._ in ihrem Intimbereich und an ihrem Po berührt; B._ habe zudem seinen Penis angefasst. A._ ist insoweit im Wesentlichen geständig. Bestritten wird von ihm insbesondere, dass er B._ überdies im Intimbereich "geleckt" und seine Finger zwischen ihren Pobacken bewegt oder einen Finger in ihren Anus eingeführt habe. A._ wurde am 28. Juli 2016 verhaftet und mit Verfügung des Bezirksgerichts Zürich, Zwangsmassnahmengericht, vom 30. Juli 2016 auf Antrag der Staatsanwaltschaft in Untersuchungshaft versetzt. Mit Verfügung vom 23. August 2016 wies das Zwangsmassnahmengericht ein Haftentlassungsgesuch von A._ ab und verlängerte die Untersuchungshaft bis zum 22. September 2016. Die dagegen erhobene Beschwerde wies das Obergericht des Kantons Zürich mit Beschluss vom 7. September 2016 ab. Mit Verfügung vom 21. September 2016 verlängerte das Zwangsmassnahmengericht die Untersuchungshaft bis zum 22. Dezember 2016. Das Obergericht wies die von A._ am 22. September 2016 erhobene Beschwerde mit Beschluss vom 5. Oktober 2016 ab. Die Regelung der Kostenauflage und allfälliger Entschädigungen behielt es dem Endentscheid vor. B. Mit Beschwerde in Strafsachen vom 7. Oktober 2016 an das Bundesgericht beantragt A._ den Beschluss der Vorinstanz vom 5. Oktober 2016 aufzuheben und ihn (eventuell unter Anordnung von Ersatzmassnahmen) aus der Untersuchungshaft zu entlassen. Ausserdem ersucht er um unentgeltliche Rechtspflege. Die Vorinstanz und die Staatsanwaltschaft verzichten auf Vernehmlassungen. Die I. öffentlich-rechtliche Abteilung hat die Angelegenheit am 23. November 2016 in öffentlicher Sitzung beraten und entschieden.