Sachverhalt:
A.
Nachdem ein erstes Leistungsgesuch mit Verfügung vom 24. August 2000 abgewiesen worden war, meldete sich der 1955 geborene A._ im September 2008 erneut bei der Invalidenversicherung zum Leistungsbezug an. Nach Abklärungen und Durchführung des Vorbescheidverfahrens sprach ihm die IV-Stelle des Kantons St. Gallen mit Verfügung vom 12. Juli 2011 eine halbe Invalidenrente ab 1. Juli 2010 bei einem Invaliditätsgrad von 54 % zu.
B.
Dagegen liess A._ Beschwerde führen. Die IV-Stelle beantragte vernehmlassungsweise, unter Abweisung der Beschwerde sei festzustellen, dass der Versicherte keinen Rentenanspruch habe. In Gutheissung des eingelegten Rechtsmittels sprach das Versicherungsgericht des Kantons St. Gallen A._ bereits mit Wirkung ab 1. April 2009 eine halbe Invalidenrente zu (Entscheid vom 25. Juni 2013).
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt die IV-Stelle des Kantons St. Gallen, der vorinstanzliche Entscheid sei aufzuheben, soweit er ab 1. April 2009 einen Anspruch auf eine halbe Rente bejahe, und die Sache sei an das kantonale Gericht zur Durchführung des Verfahrens nach <ref-law> zurückzuweisen. Ferner ersucht sie um aufschiebende Wirkung der Beschwerde.
A._ lässt auf Abweisung der Beschwerde schliessen, zudem lässt er unentgeltliche Rechtspflege beantragen. Das Bundesamt für Sozialversicherungen (BSV) verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die IV-Stelle ist zur Beschwerde legitimiert, auch wenn sie mit der Verfügung vom 26. Juli 2010 den Anspruch auf eine (Teil-) Rente noch bejahte (<ref-ruling> E. 2 S. 340 ff.).
1.2. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann unter anderem die Verletzung von Bundesrecht gerügt werden (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Das Bundesgericht legt seinem Urteil den Sachverhalt zu Grunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Artikel 95 beruht (<ref-law>).
2.
Die Vorinstanz hat dem polydisziplinären Gutachten der MEDAS vom 9. November 2010 in Bezug auf sowohl den medizinischen Sachverhalt als auch die Arbeitsfähigkeitsschätzung Beweiskraft beigemessen. Gestützt darauf hat sie für leidensangepasste Tätigkeiten eine um 50 % eingeschränkte Arbeitsfähigkeit festgestellt. Daraus resultiere ein Invaliditätsgrad von 59 % und folglich ein Anspruch auf eine halbe Invalidenrente. Die bisherige Arbeit als Maler/Gipser sei seit einem am 4. April 2008 erlittenen Unfall nicht mehr zumutbar, demnach sei der Rentenbeginn am 1. April 2009.
Aus dem MEDAS-Gutachten ergibt sich, dass "aus somatischer Sicht einzig qualitative Einschränkungen der Arbeitsfähigkeit nachvollziehbar" sind, während die Arbeitsfähigkeitsschätzung in quantitativer Hinsicht ausschliesslich auf der psychiatrischen Diagnose einer "anhaltenden somatoformen Schmerzstörung, einhergehend mit einer mittelschweren depressiven Störung mit somatischem Syndrom bei körperbezogenen Ängsten" beruht. Streitig und zu prüfen ist lediglich die (Rechts-) Frage, ob das psychische Leiden des Beschwerdegegners mit Blick auf die Rechtsprechung von <ref-ruling> eine auch rechtlich relevante Einschränkung der Arbeitsfähigkeit bewirkt.
3.
3.1. Somatoforme Schmerzstörungen und ähnliche aetiologisch-pathogenetisch unerklärliche syndromale Leidenszustände vermögen in der Regel keine lang dauernde, zu einer Invalidität im Sinne von <ref-law> führende Einschränkung der Arbeitsfähigkeit zu bewirken (<ref-ruling> E. 3 S. 280 ff.; <ref-ruling> E. 2.2.2 und 2.2.3 S. 353 f.; <ref-ruling>; <ref-ruling>; <ref-ruling>). Die - nur in Ausnahmefällen anzunehmende - Unzumutbarkeit eines Wiedereinstiegs in den Arbeitsprozess setzt das Vorliegen einer mitwirkenden, psychisch ausgewiesenen Komorbidität (vgl. dazu Urteil 9C_936/2012 vom 7. Juni 2013 E. 3.1.2 mit Hinweisen) von erheblicher Schwere, Intensität, Ausprägung und Dauer oder aber das Vorhandensein anderer qualifizierter, mit gewisser Intensität und Konstanz erfüllter Kriterien wie chronische körperliche Begleiterkrankungen und mehrjähriger Krankheitsverlauf bei unveränderter oder progredienter Symptomatik ohne längerfristige Remission, ein ausgewiesener sozialer Rückzug in allen Belangen des Lebens, ein verfestigter, therapeutisch nicht mehr angehbarer innerseelischer Verlauf einer an sich missglückten, psychisch aber entlastenden Konfliktbewältigung (primärer Krankheitsgewinn) oder schliesslich unbefriedigende Behandlungsergebnisse trotz konsequent durchgeführter Behandlungsbemühungen (auch mit unterschiedlichem therapeutischem Ansatz) und gescheiterte Rehabilitationsmassnahmen bei vorhandener Motivation und Eigenanstrengung der versicherten Person voraus (<ref-ruling> E. 2.2.3 S. 354 f.). Je mehr dieser Kriterien zutreffen und je ausgeprägter sich die entsprechenden Befunde darstellen, desto eher sind die Voraussetzungen für eine zumutbare Willensanstrengung zu verneinen (<ref-ruling> E. 4.1 S. 67 f.; <ref-ruling> E. 1.2 S. 50 f. mit Hinweisen).
3.2.
3.2.1. Für die Beurteilung der Arbeits (un) fähigkeit stützt sich die Verwaltung und im Beschwerdefall das Gericht auf Unterlagen, die von ärztlichen und gegebenenfalls auch anderen Fachleuten zur Verfügung zu stellen sind. Aufgabe des Arztes oder der Ärztin ist es, den Gesundheitszustand zu beurteilen und dazu Stellung zu nehmen, in welchem Umfang und bezüglich welcher Tätigkeiten die versicherte Person arbeitsunfähig ist. Hinsichtlich des Beweiswertes eines Arztberichtes ist entscheidend, ob dieser für die streitigen Belange umfassend ist, auf allseitigen Untersuchungen beruht, auch die geklagten Beschwerden berücksichtigt, in Kenntnis der Vorakten (Anamnese) abgegeben worden ist, in der Beurteilung der medizinischen Zusammenhänge sowie der medizinischen Situation einleuchtet und ob die Schlussfolgerungen der Experten begründet sind (<ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3a S. 352 mit Hinweis).
3.2.2. Im Rahmen der freien Beweiswürdigung (<ref-law> [SR 830.1]; vgl. <ref-ruling> E. 3.2 und 4 S. 397 ff.; Urteil I 865/06 vom 12. Oktober 2007 E. 4 mit Hinweisen) darf sich die Verwaltung - und im Streitfall das Gericht - weder über die (den beweisrechtlichen Anforderungen genügenden) medizinischen Tatsachenfeststellungen hinwegsetzen noch sich die ärztlichen Einschätzungen und Schlussfolgerungen zur (Rest-) Arbeitsfähigkeit unbesehen ihrer konkreten sozialversicherungsrechtlichen Relevanz und Tragweite zu eigen machen. Die rechtsanwendenden Behörden haben diesfalls mit besonderer Sorgfalt zu prüfen, ob die ärztliche Einschätzung der Arbeitsunfähigkeit auch invaliditätsfremde Gesichtspunkte (insbesondere psychosoziale und soziokulturelle Belastungsfaktoren) mitberücksichtigt, die vom invaliditätsrechtlichen Standpunkt aus unbeachtlich sind (vgl. <ref-ruling> E. 2.2.5 S. 355 f.; <ref-ruling> E. 5a S. 299; SVR 2012 IV Nr. 22 S. 95, 8C_302/2011 E. 2.5.1). Wo psychosoziale Einflüsse das Bild prägen, ist bei der Annahme einer rentenbegründenden Invalidität Zurückhaltung geboten (BGE <ref-ruling> E. 5a S. 299; Urteile 9C_936/2012 vom 7. Juni 2013 E. 3.2; 9C_2010/2012 vom 9. Juli 2012 E. 3.3.2)
In diesem Sinn zählt zu den vom Bundesgericht nur eingeschränkt überprüfbaren Tatsachenfeststellungen, ob eine anhaltende somatoforme Schmerzstörung resp. ein damit vergleichbares Leiden vorliegt, und bejahendenfalls, ob eine psychische Komorbidität oder weitere Umstände gegeben sind, welche die Schmerzbewältigung behindern. Als Rechtsfrage frei überprüfbar ist, ob eine festgestellte psychische Komorbidität hinreichend erheblich ist und ob einzelne oder mehrere der festgestellten weiteren Kriterien in genügender Intensität und Konstanz vorliegen, um gesamthaft den Schluss auf eine nicht mit zumutbarer Willensanstrengung überwindbare Schmerzstörung und somit auf eine invalidisierende Gesundheitsschädigung zu gestatten (<ref-ruling> E. 1.2 S. 66; SVR 2013 IV Nr. 6 S. 13, 9C_148/2012 E. 1.2; vgl. insbesondere zur Aufgabenteilung zwischen rechtsanwendender Stelle und begutachtender Arztperson das zur Publikation in der amtlichen Sammlung bestimmte Urteil 9C_850/2013 vom 12. Juni 2014 E. 3.1 und 3.2).
3.3.
3.3.1. Das kantonale Gericht hat in der depressiven Problematik ein eigenständiges Krankheitsgeschehen erblickt und mithin eine psychische Komorbidität (von erheblicher Schwere, Intensität, Ausprägung und Dauer) bejaht. Dafür hat sie sich auf verschiedene ärztliche Berichte berufen. Danach sei der Versicherte schon früher durch melancholische Züge aufgefallen, habe er als 16-jähriger einen schweren Motorradunfall erlitten und dadurch ein "schweres" Leben gehabt, sei eine depressive Episode erstmals 1991 nach dem ersten Konkurs aufgetreten und habe sich die seit der Trennung von der Ehefrau im Jahr 2002 bestehende - und damals behandelte - affektive Problematik nach dem Unfall im April 2008 bei anhaltender Schmerzproblematik und fehlender Tagesstrukturierung verstärkt.
Demgegenüber hielt der psychiatrische MEDAS-Gutachter fest, der Versicherte habe nach der Trennung von seiner Ehefrau 2002 bereits eine depressive Episode durchgemacht, sei damals fachgerecht behandelt worden und habe sich davon erholen können. Im "Zusammenhang mit den empfundenen Schmerzen" nach dem Unfall im April 2008 seien depressive Symptome erneut in den Vordergrund gerückt. Die subjektiv empfundenen Schmerzen bzw. die Somatisierung intrapsychischer Konflikte und psychosozialer Belastungen liessen sich kaum vom somatischen Syndrom innerhalb der depressiven Störung trennen. Damit ergibt sich aus dem MEDAS-Gutachten nicht, dass es sich bei der diagnostizierten depressiven Störung um ein verselbstständigtes, unabhängig von der somatoformen Schmerzstörung bestehendendes Leiden handeln soll; im Gegenteil legte der Experte einleuchtend dar, dass die Diagnosen eng miteinander verknüpft sind. Ein eigenständiger Krankheitswert der depressiven Störung lässt sich auch aus den übrigen medizinischen Unterlagen nicht ableiten, zumal die früheren Krisen vorübergehende Reaktionen auf konkrete belastende Ereignisse gewesen zu sein scheinen. Die vorinstanzliche Feststellung betreffend eine psychische Komorbidität ist somit mangels einer aktenmässigen Grundlage nicht haltbar (E. 1.2).
3.3.2. Weiter hat die Vorinstanz festgestellt, der chronische Schmerzzustand habe wenigstens teilweise eine somatische Ursache. Auch wenn dies nicht offensichtlich unrichtig sein mag (E. 1.2), ergibt sich aus dem MEDAS-Gutachten klar, dass die somatischen Beschwerden die Arbeitsfähigkeit in angepassten Tätigkeiten nicht beeinträchtigen. Von einer erheblichen chronischen körperlichen Begleiterkrankung kann somit nicht gesprochen werden, zumal als solche nicht jenes Leiden gelten kann, welches die Schmerzstörung aufrechterhält (Urteile 8C_818/2012 vom 11. März 2013 E. 6.2; 9C_709/2009 vom 14. Dezember 2009 E. 4.1).
3.3.3. Nach verbindlicher vorinstanzlicher Feststellung ist ein primärer Krankheitsgewinn "zumindest nicht auszuschliessen". Damit steht er indessen auch nicht mit überwiegender Wahrscheinlichkeit (vgl. <ref-ruling> E. 3.1 S. 59; <ref-ruling> E. 4.1 S. 325) fest.
3.3.4. Soweit das kantonale Gericht ein "gewisses" Scheitern konsequent durchgeführter Behandlung und einen mehrjährigen, chronifizierten Krankheitsverlauf mit progredienter Symptomatik ohne länger dauernde Rückbildung angenommen hat, bleibt unberücksichtigt, dass der MEDAS-Experte eine Besserung des depressiven Zustandsbildes feststellte, was er mit der fachärztlichen Behandlung durch Dr. med. B._ begründete; zudem empfahl er die Weiterführung der psychiatrisch-psychotherapeutischen Behandlung. Hinzu kommt Folgendes: Bereits im Bericht der Rheuma- und Rehabilitationsklinik C._ vom 17. April 2000, welcher der Verfügung vom 24. August 2000 zugrunde lag, wurde ein Schmerzleiden diagnostiziert und die bisherige Tätigkeit für unzumutbar gehalten, während für angepasste Arbeiten eine uneingeschränkte Arbeitsfähigkeit attestiert wurde. Sodann hat das kantonale Gericht verbindlich (E. 1.2) festgestellt, dass der Versicherte spätestens ab 1. Januar 2007 in seiner angestammten Tätigkeit als Maler wieder uneingeschränkt arbeitsfähig war, bis er im April 2008 einen Unfall erlitt. Angesichts dieser ausgewiesenen (vorübergehenden) Besserung des Gesundheitszustandes und der Arbeitsfähigkeit sind somit in Bezug auf die Dauer des Krankheitsverlaufs lediglich rund drei Jahre (vom Unfall bis zum Erlass der angefochtenen Verfügung) massgeblich.
3.3.5. Sodann hat die Vorinstanz verbindlich festgestellt, ein gewisser sozialer Rückzug müsse angenommen werden, wenngleich dieses Kriterium nicht in ausgeprägter Weise erfüllt sei. Indes kann nicht von einem ausgewiesenen sozialen Rückzug in allen Belangen des Lebens gesprochen werden, zumal der Versicherte Kontakte zur Tochter und deren Kinder sowie zu wenigen Freunden angab.
3.4. Bei der erforderlichen Gesamtbetrachtung der Morbiditätskriterien (E. 3.1 und 3.3) gibt es keine hinreichenden Gründe, dem Schmerzleiden ausnahmsweise invalidisierende Wirkung beizumessen und eine rechtlich relevante Einschränkung der Arbeitsfähigkeit anzunehmen. Die Beschwerde ist begründet.
4.
Mit diesem Ergebnis wird der Beschwerdegegner schlechter gestellt als mit der Verfügung vom 12. Juli 2011. Ein Verfahren nach <ref-law> ist nicht aktenkundig. Die Sache ist daher zu dessen Durchführung an die Vorinstanz zurückzuweisen (<ref-ruling> E. 2.3.2.2 und E. 6 S. 343).
5.
Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung der Beschwerde gegenstandslos.
6.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdegegner grundsätzlich die Gerichtskosten zu tragen (<ref-law>; vgl. auch E. 1.2). Seinem Gesuch um unentgeltliche Rechtspflege kann jedoch entsprochen werden (<ref-law>; <ref-ruling> E. 4a S. 202). Es wird indessen ausdrücklich auf <ref-law> hingewiesen, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 25. Juni 2013 wird aufgehoben und die Sache an die Vorinstanz zurückgewiesen, damit sie im Sinne von E. 4 verfahre.
2.
Dem Beschwerdegegner wird die unentgeltliche Rechtspflege gewährt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdegegner auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4.
Rechtsanwältin Christine Kessi, Procap, Olten, wird als unentgeltliche Anwältin des Beschwerdegegners bestellt, und es wird ihr für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2'400.- ausgerichtet.
5.
Das Versicherungsgericht des Kantons St. Gallen hat über die Gerichtskosten und die Parteientschädigung für das vorangegangene Verfahren unter Berücksichtigung der bereits bewilligten unentgeltlichen Prozessführung seitens des Beschwerdegegners neu zu befinden.
6.
Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 11. Juli 2014
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Kernen
Die Gerichtsschreiberin: Dormann