Sachverhalt:
A.
S._ meldete sich im Oktober 2002 bei der Invalidenversicherung an und beantragte Umschulung und/ oder eine Rente. Im Anmeldeformular wies er darauf hin, er sei vom Sozialamt dazu genötigt worden, da ihm und seiner Ehefrau sonst keine Sozialunterstützung ausbezahlt werde. Mit Verfügung vom 25. August 2003 wies die IV-Stelle des Kantons Zürich das Leistungsbegehren ab, wegen Verweigerung der Mitwirkung aufgrund der Akten. Im Januar 2004 ersuchte S._ erneut um eine Rente. Mit Verfügung vom 29. Juli 2004 verneinte die IV-Stelle einen Rentenanspruch. Nachdem am 23. Mai 2006 ein weiteres Leistungsbegehren abgewiesen worden war, wegen Verweigerung der Mitwirkung wiederum aufgrund der Akten, meldete sich der Versicherte im September 2008 erneut zum Bezug einer Rente an. Nach Abklärungen (u.a. Gutachten Dr. med. U._, FMH für Psychiatrie und Psychotherapie, vom 10. Januar 2010) und durchgeführtem Vorbescheidverfahren verneinte die IV-Stelle mit Verfügung vom 22. Dezember 2010 einen Rentenanspruch.
B.
Die Beschwerde des S._ wies das Sozialversicherungsgericht des Kantons Zürich mit Entscheid vom 13. September 2012 ab.
C.
S._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Rechtsbegehren, der Entscheid vom 13. September 2012 sei aufzuheben und ihm (revisionsweise) rückwirkend eine ganze Rente zuzusprechen; eventualiter sei ihm eine ganze Rente zuzusprechen, unter Gewährung der unentgeltlichen Rechtspflege.
Die IV-Stelle beantragt die Abweisung der Beschwerde. Das kantonale Sozialversicherungsgericht und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1.
Wurde eine Rente wegen eines zu geringen Invaliditätsgrades verweigert, wird eine neue Anmeldung nur geprüft, wenn die gesuchstellende Person glaubhaft macht, dass sich der Grad der Invalidität in einer für den Anspruch erheblichen Weise geändert hat (Art. 87 Abs. 3 und 4 [seit 1. Januar 2012: Abs. 2 und 3] IVV). Tritt die IV-Stelle auf die Neuanmeldung ein, hat sie abzuklären, ob eine solche (glaubhaft gemachte) Veränderung tatsächlich eingetreten ist. Verneinendenfalls weist sie das Rentengesuch ab (<ref-ruling> E. 3a S. 198). Die Frage, ob eine erhebliche Tatsachenänderung im Sinne von aArt. 87 Abs. 3 IVV eingetreten ist, beurteilt sich durch Vergleich der Verhältnisse im Zeitpunkt der Neuanmeldung mit denjenigen bei Erlass der letzten, auf einer materiellen Prüfung des Rentenanspruchs mit rechtskonformer Sachverhaltsabklärung, Beweiswürdigung und Ermittlung des Invaliditätsgrades beruhenden Verfügung (<ref-ruling> E. 3.2.3 S. 75 ff.; vgl. auch <ref-ruling>; Urteil 9C_236/2011 vom 8. Juli 2011 E. 2.1).
2.
Nach Auffassung der Vorinstanz ist zeitliche Vergleichsbasis die Verfügung vom 29. Juli 2004, der eine rechtskonforme Sachverhaltsabklärung zugrunde gelegen habe. Der damaligen Verzicht der IV-Stelle auf eine psychiatrische Abklärung des Gesundheitszustandes sei vertretbar gewesen. In Würdigung der Akten ist sie zum Ergebnis gelangt, der rechtserhebliche Sachverhalt sei seither bis zum Erlass der angefochtenen Verfügung vom 22. Dezember 2010 unverändert geblieben. Die IV-Stelle habe daher einen Rentenanspruch zu Recht erneut verneint.
Der Beschwerdeführer rügt, die vorinstanzliche Annahme, die Verfügung vom 29. Juli 2004 stütze sich auf eine rechtskonforme Sachverhaltsabklärung, sei offensichtlich unrichtig (Art. 97 Abs. 1 BGG). Trotz gewichtiger Indizien, dass er unter psychiatrischen Einschränkungen mit Auswirkungen auf die Arbeitsfähigkeit leide, seien keine diesbezüglichen Abklärungen vorgenommen worden. In der Entdeckung der Diagnose einer kombinierten Persönlichkeitsstörung sei eine (prozessualer) Revisionsgrund im Sinne von Art. 53 Abs. 1 ATSG zu sehen. Dass die Vorinstanz den Anspruch auf eine Invalidenrente nicht geprüft habe, verletze Bundesrecht (Art. 95 lit. a BGG).
3.
Die IV-Stelle hatte keine Veranlassung, den Versicherten vor Erlass der Verfügung vom 29. Juli 2004 psychiatrisch abzuklären. Zwar gab er in der Anmeldung vom 18. Januar 2004 an, auf Grund seiner Kindheit extrem milieugeschädigt zu sein, Angstzustände und Depressionen sowie ehemals Drogen konsumiert zu haben. Gemäss Arztbericht des Gesundheitszentrums vom 9. Juli 2004 wurden die wesentlichen psychischen Funktionen jedoch als "uneingeschränkt" taxiert (einzig zur Belastbarkeit waren keine Angaben möglich). Nachdem keine anderslautende ärztliche Anhaltspunkte vorlagen, der Versicherte auch nicht in entsprechender Behandlung stand - trotz ausdrücklicher Aufforderung, anzugeben, ob er noch bei anderen Ärzten als im Gesundheitszentrum in Behandlung sei resp. gewesen sei, erfolgte keine Mitteilung -, kann der Verwaltung in Übereinstimmung mit der Vorinstanz nicht zum Vorwurf gemacht werden, sie hätte den Sachverhalt im Zeitpunkt der Vergleichsverfügung unvollständig abgeklärt.
4.
Die Vorinstanz hat erwogen, da sowohl Dr. K._ als auch Dr. U._ von einem seit dem Jahr XXX bzw. seit der Jugend bestehenden Zustand ausgehen würden, sei anzunehmen, dass sich der rechtserhebliche medizinische Sachverhalt seit der letzten materiell begründeten Rentenabweisung mit Verfügung vom 29. Juli 2004 nicht geändert habe. Diese Feststellung entbehrt einer rechtsgenüglichen Grundlage. Eine Diagnose allein sagt wenig über das Ausmass der Einschränkung der Arbeitsfähigkeit aus, weshalb sie - entgegen der Ansicht des Beschwerdeführers - keinen (prozessualen) Revisionsgrund bildet. Wohl gibt es einen "roten Faden", der sich durch die Biografie des Beschwerdeführers zieht. Die Feststellung einer Aggravation im Gutachten von Dr. U._ vom 10. Januar 2010 und die vom Beschwerdeführer gezeigte Kooperation mit der IV-Stelle sind jedoch keine hinreichenden Nachweise dafür, dass sich seit dem Jahr 2004 nichts Rechtserhebliches in gesundheitlicher resp. erwerblicher Hinsicht verändert hat. Fachärztliche Untersuchungen oder anderweitig - erhärtete - objektive Anhaltspunkte, die sich unmittelbar auf den Vergleichszeitpunkt (29. Juli 2004) beziehen, fehlen komplett. Die vorinstanzliche Gleichsetzung von "damals" und "heute" kommt unter diesen Umständen nicht über den Beweisgrad des Möglichen hinaus, was für eine bundesrechtskonforme Sachverhaltswürdigung nicht genügt. In der mangelnden Untermauerung der Vergangenheit liegt auch die Schwäche der Einschätzungen von Dr. K._ vom 20. Februar 2008 (behandelnder Arzt) und von Dr. U._ vom 10. Januar 2010, weshalb die erwerblichen Auswirkungen nicht unbesehen auf die frühere Zeit rückbezogen werden können. Auf eine erneute Begutachtung kann verzichtet werden, zumal sich bei einer solchen die gleiche (inkomplette) Sachlage präsentieren würde. Schliesslich liegt auf der Hand, dass auf die medizinische Selbsteinschätzung des Beschwerdeführers nicht abgestellt werden kann.
5.
Hat die Vorinstanz zu Unrecht eine erhebliche Tatsachenänderung verneint, folgt die Frage nach der Invaliditätsbemessung. Es steht fest, dass der Beschwerdeführer im hier fraglichen Verfügungszeitpunkt klar vermindert arbeitsfähig ist, in welcher Hinsicht die Einschätzungen von Dr. K._ (100%ige Arbeitsunfähigkeit) und Dr. U._ (40%ige Arbeitsunfähigkeit auf dem "1. ausgeglichenen Arbeitsmarkt", womit unzweifelhaft eine unselbstständige Erwerbstätigkeit verstanden wird) grundsätzlich übereinstimmen. Die Vorinstanz hat die Abweichung im Ausmass nicht gewürdigt, was an dieser Stelle zu ergänzen ist (Art. 105 Abs. 2 BGG; <ref-ruling> E. 4.1 S. 366) : Eine psychiatrische Exploration kann von der Natur der Sache her nicht ermessensfrei erfolgen. Sie eröffnet dem begutachtenden Psychiater daher praktisch immer einen gewissen Spielraum, innerhalb dessen verschiedene medizinisch-psychiatrische Interpretationen möglich, zulässig und zu respektieren sind, sofern der Experte lege artis vorgegangen ist, was hier der Fall ist (insbesondere setzt sich Dr. U._ eingehend mit der abweichenden Meinung von Dr. K._ auseinander). Daher und unter Beachtung der Divergenz von medizinischem Behandlungs- und Abklärungsauftrag kann es nicht angehen, eine medizinische Administrativexpertise einzig in Frage zu stellen, wenn der behandelnde Arzt zu einer unterschiedlichen Einschätzungen gelangt oder an der vorgängig geäusserten abweichenden Auffassungen festhält (Urteil 9C_15/2013 vom 22. Mai 2013 E. 5.1 mit weiterem Hinweis). Im Übrigen hat auch der regionale ärztliche Dienst der IV-Stelle (RAD) das Gutachten von Dr. U._ - indem er auch auf die "Replik" von Dr. K._ vom 3. August 2010 einging - nachvollziehbar als verwertbar beurteilt. Soweit Dr. U._ den Beschwerdeführer in einer quasi-selbstständigen Tätigkeit ("Marktfahrer, Hilfsarbeiter mit grosser Autonomie") als nicht relevant eingeschränkt einschätzt, kann indessen darauf nicht abgestellt werden. Abgesehen davon, dass es sich dabei um nicht weiter konkretisierte Arbeitsgelegenheiten handelt, steht nicht mit überwiegender Wahrscheinlichkeit fest, dass dem Beschwerdeführer auf dem ausgeglichenen Arbeitsmarkt genügend solche Anstellungsmöglichkeiten offen stünden.
6.
Nach dem Gesagten (vgl. E. 4) erweist sich der ordentliche Einkommensvergleich als ungeeignet. Bei einer medizinisch ausgewiesenen Restarbeitsfähigkeit von 60 % ergibt der Prozentvergleich eine 40%ige Einbusse. Damit wird eine rentenbegründende Invalidität in gleicher Höhe erreicht. Dies gibt ab 1. März 2009 (vgl. Art. 29 IVG) Anspruch auf eine Viertelsrente.
7.
Auf die Erhebung von Gerichtskosten wird verzichtet. Dem Beschwerdeführer steht im Rahmen des teilweisen Obsiegens eine reduzierte Parteientschädigung zu.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 13. September 2012 und die Verfügung der IV-Stelle des Kantons Zürich vom 22. Dezember 2010 werden aufgehoben. Der Beschwerdeführer hat ab 1. März 2009 Anspruch auf eine Viertelsrente. Im Übrigen wird die Beschwerde abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen, soweit es nicht gegenstandslos geworden ist. Rechtsanwalt Thomas Wyss wird als unentgeltlicher Anwalt des Beschwerdeführers bestellt.
3.
Es werden keine Gerichtskosten erhoben.
4.
Die Beschwerdegegnerin hat den Rechtsvertreter des Beschwerdeführers für das bundesgerichtliche Verfahren mit Fr. 1'000.- zu entschädigen.
5.
Dem Rechtsvertreter des Beschwerdeführers wird aus der Gerichtskasse eine Entschädigung von Fr. 1'800.- ausgerichtet.
6. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Zürich zurückgewiesen.
7.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 16. September 2013
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Der Gerichtsschreiber: Fessler