Sachverhalt: A. A.a. Der serbische Staatsangehörige A._ (geb. 1985) reiste im Herbst desselben Jahres zusammen mit seiner Mutter in die Schweiz ein und war im Besitz der Niederlassungsbewilligung. Er wurde mehrfach strafrechtlich verurteilt, darunter 2005 zu sechs Monaten Gefängnis (bedingt) wegen Diebstahls, 2007 zu 18 Monaten Freiheitsstrafe (bedingt) u.a. wegen gewerbs- und bandenmässigen Diebstahls, mahrfacher Sachbeschädigung und mehrfachen Hausfriedensbruchs und am 11. März 2011 zu 42 Monaten Freiheitsstrafe u.a. wegen mehrfachen Raubes. Im Urteil vom 16. März 2011 wurde der Vollzug der Freiheitsstrafe zugunsten einer stationären Massnahme für junge Erwachsene aufgeschoben. A.b. Mit Verfügung vom 11. Dezember 2012 widerrief das Migrationsamt des Kantons Zürich die Niederlassungsbewilligung von A._ und ordnete an, dass dieser die Schweiz unverzüglich nach Beendigung der stationären Massnahme zu verlassen habe. Die letztinstanzlich hiegegen erhobene Beschwerde wies das Bundesgericht mit Urteil vom 20. Februar 2015 ab, soweit es darauf eintrat (Verfahren 2C_438/2014). A.c. A._ hatte am 31. Oktober 2014 die 1980 geborene Schweizerin B._ geheiratet. Mit ihr hat er den gemeinsamen Sohn C._ (geb. im Februar 2015). Die Ehe wurde am 4. November 2015 geschieden, C._ unter der elterlichen Sorge beider Eltern belassen und die Obhut der Mutter zugeteilt. A._ erhielt ein Besuchsrecht. Er war zwischenzeitlich arbeitslos (zit. Urteil 2C_438/2014 lit. A.a) und hat nach Angaben seines Rechtsvertreters auch heute "keinen Anstellungsvertrag"; sodann dürften sich seine Schulden "auf insgesamt weit über Fr. 100'000.-- belaufen". B. Mit Gesuch vom 13. März 2015 beantragte A._ beim Migrationsamt des Kantons Zürich, es sei ihm ein "festes Aufenthaltsrecht (Niederlassung, eventualiter Aufenthaltsbewilligung) " zu gewähren. Mit Verfügung vom 5. Oktober 2015 wies das Amt das Gesuch ab. Diese Verfügung bestätigte das Verwaltungsgericht des Kantons Zürich mit Urteil vom 31. März 2016 kantonal letztinstanzlich. C. Mit Eingabe vom 11. Mai 2016 führt A._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Antrag, das letztgenannte Urteil aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht. Die Akten und Vernehmlassungen sind eingeholt worden; mit Verfügung vom 12. Mai 2016 wurde der Beschwerde zudem - antragsgemäss - aufschiebende Wirkung zuerkannt.