Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Streitig und zu prüfen ist vorab, ob der Beschwerdeführer Anspruch auf berufliche Eingliederungsmassnahmen in Form von Umschulung (<ref-law>), allenfalls auch Berufsberatung (<ref-law>) und Arbeitsvermittlung (<ref-law>) hat.
a) Nach <ref-law> hat der Versicherte Anspruch auf Umschulung auf eine neue Erwerbstätigkeit, wenn die Umschulung infolge Invalidität notwendig ist und dadurch die Erwerbsfähigkeit voraussichtlich erhalten oder wesentlich verbessert werden kann. Gemäss <ref-law> gelten als Umschulung Ausbildungsmassnahmen, die Versicherte nach Abschluss einer erstmaligen beruflichen Ausbildung oder nach Aufnahme einer Erwerbstätigkeit ohne vorgängige berufliche Ausbildung wegen ihrer Invalidität zur Erhaltung oder wesentlichen Verbesserung der Erwerbsfähigkeit benötigen.
b) Invalid im Sinne von <ref-law> ist der Versicherte, wenn er wegen der Art und Schwere des Gesundheitsschadens im bisher ausgeübten Beruf und in den ihm ohne zusätzliche berufliche Ausbildung offen stehenden zumutbaren Erwerbstätigkeiten eine bleibende oder längere Zeit dauernde Erwerbseinbusse von mindestens etwa 20 % erleidet (AHI 1997 S. 80 Erw. 1b; ZAK 1984 S. 91 oben). Bei der Beurteilung, ob die nach der Rechtsprechung geforderte Erheblichkeitsschwelle erreicht ist, sind, insbesondere bei Berufen mit tiefen Anfangslöhnen, neben den aktuellen Verdienstmöglichkeiten im Rahmen einer Prognose weitere Faktoren wie Lohnentwicklung und Aktivitätsdauer mit zu berücksichtigen (<ref-ruling> ff.). Die Umschulung hat den Versicherten in die Lage zu versetzen, eine seiner früheren Tätigkeit möglichst gleichwertige Erwerbstätigkeit auszuüben (<ref-ruling> Erw. 3b/bb, 100 V 19, je mit Hinweisen).
Der Versicherte hat Anspruch auf eine annähernd gleichwertige, nicht dagegen auf eine höherwertige Ausbildung, es sei denn, die erwerblichen Auswirkungen des Gesundheitsschadens lassen sich nur auf diese Weise hinreichend beheben (ZAK 1988 S. 467). Die Gleichwertigkeit bezieht sich nicht in erster Linie auf das Ausbildungsniveau als solches, sondern auf die nach erfolgter Ausbildung zu erwartenden Verdienstmöglichkeiten (ZAK 1988 S. 470, 1978 S. 517); bei der Beurteilung der Gleichwertigkeit ist indessen auch die mit der angestrebten Ausbildung verbundene (voraussichtliche) künftige Entwicklung der Erwerbsmöglichkeiten zu berücksichtigen (AHI 1997 S. 83; ferner <ref-ruling> ff.).
2.- a) Auf Grund der ärztlichen Angaben ist anzunehmen, dass der Beschwerdeführer den bisherigen Beruf als Bauhilfsarbeiter krankheitsbedingt nicht mehr auszuüben vermag. Jedenfalls ist er im Rahmen der bisherigen Tätigkeit in einem Grad beeinträchtigt, dass die Voraussetzungen für eine Umschulung grundsätzlich gegeben sind. Dass er keine Berufslehre absolviert hat und stets als Hilfsarbeiter tätig gewesen ist, schliesst einen Anspruch nach <ref-law> nicht aus. Als Umschulung in Betracht fällt auch eine Anlehre oder eine Vorbereitung - beispielsweise in Form eines Sprachkurses (vgl. AHI 1997 S. 79) - auf eine andere, besser entlöhnte Tätigkeit, welche es dem Versicherten erlaubt, die mit der erforderlichen Umstellung auf eine geeignete leichtere Tätigkeit verbundene Verdiensteinbusse ganz oder teilweise auszugleichen.
Die Verwaltung hat den Anspruch auf berufliche Eingliederungsmassnahmen nicht umfassend geprüft. Die angefochtene Verfügung beschränkt sich auf die Feststellung, dass die Vermittlung eines adäquaten Arbeitsplatzes aus invaliditätsfremden Gründen zur Zeit nicht möglich sei. Die Feststellung stützt sich auf die Ausführungen der Berufsberaterin der IV-Stelle im Bericht vom 24. Februar 1998, wonach eine berufliche Wiedereingliederung des Versicherten aus invaliditätsfremden Gründen nicht mehr möglich ist. Um was für Gründe es sich dabei handelt, wird im Bericht nicht näher ausgeführt. Festgestellt wird lediglich, dass sämtliche Bemühungen der Organe der Arbeitslosenversicherung, dem Versicherten Arbeit zu vermitteln, erfolglos geblieben seien.
Während sechs Monaten sei er in einem Beschäftigungsprogramm integriert gewesen, wo er mit Einsatz gearbeitet habe und seine Leistungen "nicht so schlecht" gewesen seien; er habe jedoch sehr einfache und wenig anspruchsvolle Arbeiten ausführen müssen. Es wird damit allenfalls eine Arbeitsvermittlung (<ref-law>) als aussichtslos bezeichnet, jedoch nichts über die Notwendigkeit und die Erfolgsaussichten einer Umschulung ausgesagt. Wenn die Vorinstanz in diesem Zusammenhang auf das vorgerückte Alter des (1946 geborenen) Beschwerdeführers hinweist, so genügt dies nicht, um die Erfolgsaussichten beruflicher Eingliederungsbemühungen zu verneinen. Der Sachverhalt bedarf daher zusätzlicher Abklärungen.
b) Als ungenügend abgeklärt erweisen sich auch der medizinische Sachverhalt und die Frage nach den erwerblichen Auswirkungen der diagnostizierten gesundheitlichen Beeinträchtigungen. Seitens des Diabetes mellitus scheint sich die Beeinträchtigung auf eine täglich zweimalige Insulin-Injektion sowie eine Fussschwellung bei längeren Gehstrecken zu beschränken. Bezüglich der andern Leiden fehlen jegliche Angaben zur Relevanz der Befunde für die Arbeitsfähigkeit des Beschwerdeführers. Aus den Arztberichten geht insbesondere nicht schlüssig hervor, inwieweit der Beschwerdeführer auch im Rahmen einer körperlich leichteren Tätigkeit in der Arbeitsfähigkeit beeinträchtigt ist.
Während sich Dr. med. G._ im Bericht vom 9. August 1996 hiezu nicht ausspricht, führt Dr. med. S._ in der ergänzenden Stellungnahme vom 26. Juni 1997 aus, der Versicherte sei seines Erachtens für eine körperlich leichte Tätigkeit mindestens zu 70 % arbeitsfähig. Gemäss einer im Bericht der Berufsberaterin der IV-Stelle erwähnten Auskunft von Dr. med. G._ soll der Versicherte für leichte körperliche Arbeiten sogar voll arbeitsfähig sein.
Angesichts dieser teils unbestimmten, teils widersprüchlichen Angaben wäre die IV-Stelle zur Vornahme ergänzender Abklärungen gehalten gewesen, zumal der Versicherte im Rahmen eines Beschäftigungsprogramms der Arbeitslosenversicherung anscheinend voll gearbeitet hat. Mangels entsprechender Abklärungen lässt sich nicht zuverlässig beurteilen, inwieweit der Beschwerdeführer auch im Rahmen einer geeigneten leichteren Tätigkeit in der Arbeitsfähigkeit beeinträchtigt ist und ob gegebenenfalls selbst bei voller Arbeitsfähigkeit eine invaliditätsbedingte Notwendigkeit beruflicher Eingliederungsmassnahmen zum Ausgleich allfälliger Lohnunterschiede besteht. Die Sache ist daher an die Verwaltung zurückzuweisen, damit sie ergänzende medizinische und berufliche Abklärungen, erforderlichenfalls in Form eines stationären Abklärungsaufenthaltes, vornehme und hierauf über den Anspruch des Beschwerdeführers auf berufliche Eingliederungsmassnahmen befinde.
c) Nach dem Gesagten ist die Verfügung vom 26. November 1998 aufzuheben. Über den Rentenanspruch wird die Verwaltung aufgrund der Ergebnisse der vorzunehmenden Abklärungen und nach allfälliger Durchführung beruflicher Eingliederungsmassnahmen neu zu verfügen haben. Bei der Neubeurteilung des Rentenanspruchs werden, soweit erforderlich, die vom Beschwerdeführer gegen die Invaliditätsbemessung vorgebrachten Einwendungen zu prüfen sein.
3.- Entsprechend dem Ausgang des Verfahrens hat der Beschwerdeführer Anspruch auf Parteientschädigung (Art. 159 Abs. 2 OG). Das Begehren um Gewährung der unentgeltlichen Verbeiständung (Art. 152 Abs. 2 OG) erweist sich damit als gegenstandslos.

Demnach erkennt das Eidg. Versicherungsgericht:
I. Die Verwaltungsgerichtsbeschwerde wird in dem Sinne
gutgeheissen, dass der Entscheid des Verwaltungsgerichts
des Kantons Appenzell Ausserrhoden vom 20. Oktober 1999 sowie die Verfügung vom 26. November
1998 aufgehoben werden und die Sache an die IV-Stelle
des Kantons Appenzell Ausserrhoden zurückgewiesen
wird, damit sie, nach erfolgter Abklärung im Sinne der
Erwägungen, über den Leistungsanspruch neu verfüge.
II. Es werden keine Gerichtskosten erhoben.
III. Die IV-Stelle des Kantons Appenzell Ausserrhoden hat dem Beschwerdeführer für das Verfahren vor dem Eidgenössischen Versicherungsgericht eine Parteientschädigung
von Fr. 2'500.- (einschliesslich Mehrwertsteuer)
zu bezahlen.
IV. Das Verwaltungsgericht des Kantons Appenzell Ausserrhoden wird über eine Parteientschädigung anstelle der unentgeltlichen Verbeiständung für das vorinstanzliche
Verfahren zu befinden haben.
V. Dieses Urteil wird den Parteien, dem Verwaltungsgericht
des Kantons Appenzell Ausserrhoden und dem Bundesamt
für Sozialversicherung zugestellt.
Luzern, 4. Juli 2000
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der II. Kammer:
Die Gerichtsschreiberin: