Sachverhalt:
A.
A.a. Mit Verfügung vom 5. April 2006, bestätigt mit Einspracheentscheid vom 9. August 2006, sprach die IV-Stelle des Kantons Appenzell Ausserrhoden dem 1952 geborenen P._ eine Viertelsrente ab 1. November 2001, eine ganze Rente ab 1. Februar 2005 (unter Berücksichtigung der Folgen eines am 6. Februar 2005 erlittenen Verkehrsunfalles) sowie eine Viertelsrente ab 1. September 2005 zu. Das Verwaltungsgericht Appenzell Ausserrhoden wies eine hiegegen erhobene Beschwerde des P._ mit Entscheid vom 25. April 2007 ab, worauf dieser Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht führen liess. Das Bundesgericht hiess diese mit Urteil vom 6. Mai 2008 (9C_494/2007) teilweise gut, hob den angefochtenen Entscheid sowie den Einspracheentscheid auf, soweit darin der Anspruch auf Arbeitsvermittlung verneint wurde, und wies die Sache zur Durchführung eines Mahn- und Bedenkzeitverfahren und anschliessender Neuverfügung über den Anspruch auf berufliche Massnahmen an die IV-Stelle zurück. Im Übrigen wies es die Beschwerde ab.
A.b. In der Folge führte die IV-Stelle verschiedene Gespräche mit P._, veranlasste eine berufliche Abklärung im Verzahnungsprogramm S._ (vom 18. August bis 28. November 2008) und forderte ihn insbesondere auf, seine Stellensuche zu intensivieren. Nachdem eine Eingliederung in den ersten Arbeitsmarkt misslungen und auch die Teilnahme am Einsatzprogramm nicht erfolgreich verlaufen war, schloss die Invalidenversicherung die Arbeitsvermittlung ab (Mitteilung vom 18. Februar 2009).
Im August 2009 leitete die IV-Stelle ein Rentenrevisionsverfahren ein, in dessen Rahmen P._ eine gesundheitliche Verschlechterung geltend machte und die IV-Stelle namentlich einen Bericht des Hausarztes Dr. med. G._, FMH für Allgemeinmedizin, vom 9. September 2009, sowie eine Beurteilung des Regionalen Ärztlichen Dienstes (RAD; Dr. med. W._) vom 28. Januar 2010 einholte. Auf Empfehlung des Dr. med. W._ veranlasste sie eine Begutachtung in der Medas Y._ vom 23. Juni 2010. Nach erneuter Stellungnahme des RAD-Arztes vom 24. Juni 2010 verfügte die IV-Stelle am 2. August 2010, es bestehe weiterhin Anspruch auf die bisherige Rente bei einem IV-Grad von 46 %.
Am 11. August 2010 teilte die IV-Stelle P._ mit, sie sei bereit, erneut Arbeitsvermittlungsbemühungen aufzunehmen, sofern er zum einen eine längerfristige, stabile Alkoholabstinenz durch den behandelnden Arzt ausweisen könne und zum andern die medizinisch ausgewiesene Arbeitsfähigkeit von 60 % in einer adaptierten Tätigkeit anerkenne sowie "in diesem Rahmen uneingeschränkt an Eingliederungsmassnahmen teilnehme".
B.
Am 23. August 2010 liess P._ gegen die Verfügung vom 2. August 2010 beim Verwaltungsgericht Appenzell Ausserrhoden Beschwerde erheben und deren Aufhebung sowie die Zusprechung einer ganzen Rente, eventualiter die (vorgängige) Durchführung beruflicher Massnahmen beantragen. Nachdem die IV-Stelle Ende Oktober 2010 erneut Arbeitsvermittlung zugesprochen hatte, sistierte das Verwaltungsgericht auf Ersuchen des Versicherten das Verfahren. Die IV-Stelle veranlasste in der Folge ein Arbeitstraining bei der O._ GmbH vom 9. bis 25. Februar 2011 (Abschlussbericht vom 27. April 2011). Am 23. September 2011 orientierte die IV-Stelle den Rechtsvertreter des Versicherten, die Arbeitsvermittlungsbemühungen (welche P._ nicht aktiv unterstützt habe) seien aus invaliditätsfremden Gründen erfolglos geblieben und würden abgeschlossen. Mit Eingabe vom 30. September 2011 ersuchte sie beim Gericht um Weiterführung des Verfahrens. Am 9. Mai 2012 wies das per 1. Januar 2011 für Beschwerden im Sozialversicherungsrecht zuständig gewordene Obergericht Appenzell Ausserrhoden (Justizgesetz vom 13. September 2010 [bGS 145.31] Art. 28 lit. b) die Beschwerde ab.
C.
P._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen und unter Aufhebung des angefochtenen Entscheides die Zusprechung einer ganzen Rente ab 1. November 2001 beantragen. Eventualiter sei die IV-Stelle zur Durchführung beruflicher Massnahmen und neuem Entscheid über den Rentenanspruch zu verpflichten.

Erwägungen:
1.1. 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 zugrunde, 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>).
1.2. Die gesetzliche Kognitionsbeschränkung gilt namentlich für die Einschätzung der gesundheitlichen und leistungsmässigen Verhältnisse (<ref-law>), wie sie sich bei der revisionsweisen Anpassung einer Invalidenrente nach <ref-law> wegen Tatsachenänderungen (Gesundheitszustand, Arbeits- und Erwerbsunfähigkeit usw.) im revisionsrechtlich massgeblichen Vergleichszeitraum (z.B. Urteil 8C_409/2012 vom 10. Dezember 2012 E. 1.2 mit Hinweis auf <ref-ruling>) entwickelt haben.
2.
2.1. Der rentenzusprechenden Verfügung vom 5. April 2006 lag die Annahme zu Grunde, der Versicherte wäre (nach Abheilung der Unfallfolgen) ab 20. August 2005 in einer zumutbaren Arbeitstätigkeit zu 60 % erwerbsfähig, so dass bei einem Valideneinkommen von Fr. 59'660.- und einem Invalidenlohn von Fr. 32'217.- ein Invaliditätsgrad von 46 % resultierte. Streitig und zu prüfen ist zunächst, ob der angefochtene Entscheid Bundesrecht verletzt, soweit darin die Voraussetzungen für eine Rentenrevision verneint werden.
2.2. Das kantonale Gericht legt die Rechtsgrundlagen zur Revision von Invalidenrenten (<ref-law>; <ref-ruling> E. 3.5 S. 349; <ref-ruling> E. 5.4 S. 114) sowie zum Beweiswert und zur Beweiswürdigung medizinischer Berichte, namentlich auch bei Diskrepanzen zwischen ärztlichen Beurteilungen und Einschätzungen beruflicher Abklärungspersonen (<ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3a S. 352 mit Hinweis; Urteile 9C_572/2012 vom 18. Oktober 2012 E. 2.2.1 und 9C_737/2011 vom 16. Oktober 2012 E. 3.3 je mit weiteren Hinweisen) zutreffend dar.
3.
3.1. Die Vorinstanz würdigte die medizinischen Berichte sowie der Beurteilungen der beruflichen Abklärungspersonen pflichtgemäss und erwog, seit der ursprünglichen Rentenzusprache vom 5. April 2006 sei keine rechtserhebliche gesundheitliche Verschlechterung eingetreten, weshalb die Revisionsvoraussetzungen nicht gegeben seien. Insbesondere vermöchten die Abklärungsberichte des Verzahnungsprogramms S._ vom 2. Dezember 2008 und der O._ GmbH vom 21. Februar 2011 den Beweiswert des Medas-Gutachtens nicht zu beeinträchtigen. Das Valideneinkommen sei im Erstverfahren basierend auf Angaben des Arbeitgebers festgesetzt worden, " scheinbar " ohne Berücksichtigung von Schichtzulagen und Leistungsprämien. Das Einkommen beruhe daher (grundsätzlich) auf einer unzutreffenden tatbeständlichen Würdigung und damit auf einem Willensbildungsfehler der Behörde. Diesen hätte der Versicherte aber auf dem ordentlichen Rechtsmittelweg im Erstverfahren, spätestens mit Revisionsgesuch beim Bundesgericht geltend machen müssen, was indes unterblieben sei. Von einem Rechnungsfehler könne nicht gesprochen werden. (Auch) eine Wiedererwägung komme nicht mehr in Frage, nachdem es selbst das Valideneinkommen (mit Entscheid vom 25. April 2007) "explizit" auf Fr. 57'200.- festgesetzt habe.
3.2. Der Beschwerdeführer macht geltend, seine Ansprüche seien zu Unrecht verneint worden. Die Berichte über die beruflichen Abklärungen belegten als neue erhebliche Beweismittel die Unrichtigkeit der Rentenverfügungen vom 5. April und 19. September 2006. Er rügt, die Vorinstanz habe sich mit keinem Wort zur gemäss <ref-law> angezeigten Revision geäussert, mindestens fehle eine klärende medizinische Stellungnahme. Das völlige Ausserachtlassen der Abklärungen im Verzahnungsprogramm S._ sowie bei der O._ GmbH verstosse gegen <ref-law>. Sodann sei der Invaliditätsgrad nicht wiederzuerwägen, sondern zu berichtigen, weil die IV-Stelle bloss die einschlägigen Angaben zum Valideneinkommen in den Akten der Unfallversicherung übersehen und die Gerichte die fehlerhaft festgesetzte Höhe undiskutiert übernommen hätten.
4.
4.1. Die Beweiswürdigung des kantonalen Gerichts, welches sich sowohl mit den medizinischen Beurteilungen als auch mit den beruflichen Abklärungsberichten pflichtgemäss auseinandergesetzt und insbesondere nachvollziehbar begründet dargelegt hat, weshalb auf das Medas-Gutachten vom 23. Juni 2010 abzustellen und entgegen den beruflichen Abklärungsberichten nicht eine (erst) nach beruflichen Massnahmen verwertbare, nur "geringe" Arbeitsfähigkeit anzunehmen sei, genügt in allen Teilen den bundesrechtlichen Anforderungen. Zu Recht berücksichtigte die Vorinstanz, dass die Medas-Gutachter die attestierten Einschränkungen mit medizinischen Untersuchungsergebnissen begründeten, während die beruflichen Abklärungspersonen entscheidend auf ihre subjektive Wahrnehmung und die (geäusserten) Befindlichkeiten des Versicherten abstellten. Weil keinerlei Anhaltspunkte auf eine zweifellose Unrichtigkeit der ursprünglichen Rentenverfügung (en) hindeuteten (zu den strengen Voraussetzungen an Revisionsgründe, wenn diese - wie hier - im Bereich materieller Anspruchsvoraussetzung geltend gemacht werden, deren Beurteilung massgeblich auf Schätzung oder Beweiswürdigung beruht, vgl. z.B. Urteil 9C_955/2012 vom 13. Februar 2013 E. 3.3.1), hat sich die Vorinstanz zu Recht darauf beschränkt, die Rentenrevisionsvoraussetzungen nach <ref-law> zu verneinen, ohne eine prozessuale Revision (<ref-law>) explizit auszuschliessen. Für beweisrechtliche Weiterungen bestand weder im kantonalen Beschwerdeverfahren Anlass, noch ist ein solcher letztinstanzlich auszumachen. Aktenwidrig ist die Behauptung, das kantonale Gericht habe die beruflichen Abklärungsberichte "rechtswidrig" vollständig ausser Acht gelassen, nachdem im angefochtenen Entscheid - wie dargelegt - einlässlich und begründet dargelegt wurde, weshalb die Berichte des Verzahnungsprogramms S._ und der O._ GmbH das Medas-Gutachten nicht in Frage zu stellen vermöchten.
4.2. Mit Bezug auf die bereits im vorinstanzlichen Verfahren erhobenen und letztinstanzlich wiederholten Einwände gegen die Höhe des Valideneinkommens stellte das kantonale Gericht letztinstanzlich verbindlich fest, der mutmassliche Lohn ohne Behinderung sei (im IV-Verfahren) "scheinbar" ohne Schichtzulagen und Leistungsprämien festgesetzt worden und erwog, dabei handle es sich um einen Willensbildungsfehler der Behörde (E. 3.1 hievor). In der Tat stützte sich die IV-Stelle bei der Festsetzung des Valideneinkommens auf die Angaben der ehemaligen Arbeitgeberfirma, welche mit Fragebogen vom 19. September 2001 den AHV-pflichtigen Lohn des Beschwerdeführers auf Fr. 4'400.- monatlich beziffert hatte, ohne zusätzliche Schichtzulagen und Leistungsprämien zu erwähnen. Demgegenüber ermittelte die Schweizerische Unfallversicherung (SUVA) den Jahresverdienst unter Einbezug von Kinder- und Schichtzulagen sowie einer Leistungsprämie (Bericht vom 14. Mai 2001), was dem seit September 2001 - auch im unfallversicherungsrechtlichen Verfahren - rechtskundig vertretenen Versicherten somit längst bekannt gewesen sein musste. Wenn er unter Berufung auf Akten der SUVA aus dem Jahr 2001 rund sieben Jahre benötigte, um den Mangel aufzuspüren, verbietet es sich bereits aus diesem Grund, von einer offenbaren oder klaren Unrichtigkeit zu sprechen (Urteil I 172/06 vom 26. April 2006 E. 2.3). Eine Berichtigung ist ausgeschlossen. Der Beschwerdeführer hätte nach den zutreffenden Erwägungen der Vorinstanz entsprechende Einwände auf dem ordentlichen Rechtsweg (<ref-law>) geltend machen müssen (<ref-ruling> E. 3.1 S. 326). Dies hat er aber in seinen zahlreichen Eingaben an IV-Stelle, Vorinstanz und Bundesgericht unbestrittenermassen nie getan, sondern die Höhe des Validenlohnes erst im Juni 2008 in Frage gestellt.
5.
5.1. Was schliesslich die Rüge betrifft, die Beschwerdegegnerin " verweigere " seit Jahren berufliche Massnahmen - über welche die Vorinstanz in Ausdehnung des Streitgegenstandes befunden hatte - und verhalte sich in diesem Zusammenhang treuwidrig, stellte die Vorinstanz letztinstanzlich verbindlich fest, die IV-Stelle habe den Versicherten "über Jahre hinweg unterstützend, beratend und vermittelnd bei der Stellensuche unterstützt". Sie erwog, mit Blick auf die konkreten Verhältnisse (Alter, gesundheitliche Schwierigkeiten, langjährige Absenz vom Arbeitsmarkt) seien bereits aus objektiven Gründen die Chancen auf einen Arbeitsplatz in der freien Wirtschaft eher gering. Die angemessenen, zweckmässigen Arbeitsvermittlungsbemühungen der Beschwerdegegnerin seien, bei fehlender subjektiver Eingliederungsbereitschaft, erfolglos geblieben. Realistischerweise könne in Zukunft ebenfalls kein positives Ergebnis erwartet werden, so dass - in Nachachtung des Verhältnismässigkeitsprinzips - kein Anspruch auf (weitere) Arbeitsvermittlung bestehe. Nicht erfüllt seien die Voraussetzungen für eine Umschulung in Anbetracht des nahen Pensionsalters, der langjährigen Absenz vom Arbeitsmarkt und namentlich weil die zumutbaren Tätigkeiten keine besondere Ausbildung verlangten.
5.2. Die Vorbringen des Beschwerdeführers vermögen auch in diesem Punkt keine Bundesrechtswidrigkeit darzutun. Aktenwidrig ist zunächst die Behauptung, die Beschwerdegegnerin habe der O._ GmbH keinen Vermittlungsauftrag erteilt. Dass durchaus Vermittlungsbemühungen stattfanden, lässt sich dem Schreiben der O._ GmbH vom 30. Mai 2011 zweifelsfrei entnehmen, worin diese ihre Abklärungsergebnisse darlegte und wörtlich festhielt: " Wir können zurzeit nicht vermittelnd wirken, es sind uns keine Stellen bekannt, die frei wären. " Im Übrigen ist die vorinstanzlich geschützte Einstellung der Arbeitsvermittlung in keiner Weise zu beanstanden, namentlich nicht angesichts der langjährigen, auch an der fehlenden subjektiven Eingliederungsbereitschaft des Beschwerdeführers gescheiterten Bemühungen (vgl. Urteil I 589/98 vom 21. Juni 1999, publiziert in: AHI 2000 198). Entgegen den Ausführungen des Beschwerdeführers wurde ein Umschulungsanspruch nie (rechtsverbindlich) zugesichert, insbesondere nicht in der Vernehmlassung der Beschwerdegegnerin vom 18. März 2003 (worin diese lediglich festhielt, die Verfügung vom 3. Dezember 2002 verwehre einen Umschulungsanspruch nicht) und im vorinstanzlichen Urteil vom 18. Februar 2004 (wo das kantonale Gericht erwog, eine spätere Umschulung sei durch die damals sinnvollere Arbeitsvermittlung nicht ausgeschlossen). Von einem treuwidrigen Verhalten kann keine Rede sein. Schliesslich hält der vorinstanzlich verneinte Anspruch auf Umschulung auch mit Blick darauf vollumfänglich vor Bundesrecht Stand, dass der subjektiv nicht eingliederungsbereite Versicherte seit 1979 als angelernter Maschinenführer tätig gewesen war und ihm nach Einschätzung der Medas-Gutachter aus medizinischer Sicht weiterhin ein breites Feld an Tätigkeiten offen stehen würde.
6.
Das Verfahren ist kostenpflichtig (<ref-law>). Die Gerichtskosten werden dem unterliegenden Beschwerdeführer auferlegt (Art. 65 Abs. 4 lit. a in Verbindung mit <ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Parteien, dem Obergericht von Appenzell Ausserrhoden, der Ostschweizerischen Ausgleichskasse für Handel und Industrie, St. Gallen, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 6. Juni 2013
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Meyer
Die Gerichtsschreiberin: Bollinger Hammerle