A.- Der 1964 geborene, aus dem Kosovo stammende M._ reiste 1986 erstmals in die Schweiz, wo er mit Ausnahme der Jahre 1987 und 1991 als Saisonnier verschiedene Arbeiten verrichtete. Seit 1992 war er als Bäckergehilfe in der Firma B._ tätig, als im Mai 1995 zunehmend Nacken- sowie linksseitige Kopfschmerzen auftraten. Infolge dieser Beschwerden war er ab 28. November 1995 zu 100 % arbeitsunfähig und bezog bis 16. Dezember 1997 Krankentaggelder. Nachdem er am 21. Juli 1997 einen Sturz erlitten hatte, klärte der zuständige Unfallversicherer, die Basler Versicherungs-Gesellschaft (nachfolgend: "Basler"), die medizinischen Verhältnisse ab und übernahm in der Folge die Kosten einiger ärztlicher Behandlungen. Am 9. Februar 1998 stellte M._, welcher sich bis zu diesem Zeitpunkt im Kanton Graubünden aufgehalten hatte, bei der Empfangsstelle in K._ ein Asylgesuch, woraufhin er am 13. Februar 1998 als Asylbewerber dem Kanton Appenzell Appenzell Ausserrhoden zugewiesen und als solcher in der Gemeindeunterkunft C._ untergebracht wurde.
Mit Verfügung vom 4. November 1998 lehnte die "Basler" die Ausrichtung von weitergehenden Versicherungsleistungen ab, woran sie mit Einspracheentscheid vom 8. Juli 1999 festhielt.
B.- Auf die hiegegen erhobene Beschwerde trat das Verwaltungsgericht von Appenzell Ausserrhoden nicht ein, da
das Verwaltungsgericht des Kantons Graubünden zuständig sei (Entscheid vom 8. Dezember 1999).
C.- M._ lässt Verwaltungsgerichtsbeschwerde führen und beantragen, in Aufhebung des angefochtenen Entscheids sei die Vorinstanz zu verpflichten, auf die Beschwerde einzutreten. Ferner ersucht er um Gewährung der unentgeltlichen Verbeiständung.
Während die "Basler" und das Verwaltungsgericht von Appenzell Ausserrhoden auf Abweisung der Verwaltungsgerichtsbeschwerde schliessen, verzichtet das zum Verfahren beigeladene Verwaltungsgericht des Kantons Graubünden auf eine Stellungnahme. Das Bundesamt für Sozialversicherung hat sich nicht vernehmen lassen.

Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- a) Der angefochtene Gerichtsentscheid vom 8. Dezember 1999, womit das Verwaltungsgericht von Appenzell Ausserrhoden auf die Beschwerde gegen den Einspracheentscheid der "Basler" vom 8. Juli 1999 mangels örtlicher Zuständigkeit nicht eingetreten ist, stellt eine Verfügung im Sinne von Art. 97, 98 lit. g und 98a OG in Verbindung mit Art. 128 OG dar (<ref-ruling> Erw. 1, 120 V 349 Erw. 2b, je mit Hinweisen). Auf die hiegegen erhobene Verwaltungsgerichtsbeschwerde ist demnach einzutreten.
b) Da es sich bei der angefochtenen Verfügung nicht um die Bewilligung oder Verweigerung von Versicherungsleistungen handelt, hat das Eidgenössische Versicherungsgericht nur zu prüfen, ob das vorinstanzliche Gericht Bundesrecht verletzt hat, einschliesslich Überschreitung oder Missbrauch des Ermessens, oder ob der rechtserhebliche Sachverhalt offensichtlich unrichtig, unvollständig oder unter Verletzung wesentlicher Verfahrensbestimmungen festgestellt worden ist (Art. 132 in Verbindung mit Art. 104 lit. a und b sowie Art. 105 Abs. 2 OG).
2.- Nach <ref-law> ist für die Beurteilung von Beschwerden gegen Einspracheentscheide das Versicherungsgericht desjenigen Kantons zuständig, in welchem der Betroffene seinen Wohnsitz hat (Satz 1; vgl. auch <ref-ruling> Erw. 6e). Befindet sich der Wohnsitz im Ausland, so ist das Versicherungsgericht des Kantons zuständig, in dem sich der letzte schweizerische Wohnsitz des Betroffenen befand oder in dem sein letzter schweizerischer Arbeitgeber Wohnsitz hat; lassen sich beide nicht ermitteln, so ist das Versicherungsgericht des Kantons zuständig, in dem der Versicherer seinen Sitz hat (Satz 2).
Der Gerichtsstand am Wohnsitz des Versicherten richtet sich nach dem zivilrechtlichen Wohnsitz gemäss <ref-law> (EVGE 1963 S. 21; Rumo-Jungo, Rechtsprechung des Bundesgerichts zum Sozialversicherungsrecht, Bundesgesetz über die Unfallversicherung, Zürich 1995, S. 382). Die örtliche Kompetenz bestimmt sich nach den Verhältnissen zur Zeit der Klageerhebung (EVGE 1940 S. 39 f.; Rumo-Jungo, a.a.O., S. 382). Gemäss <ref-law> befindet sich der massgebende zivilrechtliche Wohnsitz einer Person an dem Ort, wo sie sich mit der Absicht dauernden Verbleibens aufhält und den sie sich zum Mittelpunkt ihrer Lebensinteressen gemacht hat (<ref-ruling> Erw. 2a, 97 II 3 Erw. 3, 85 II 322). Für die Begründung eines Wohnsitzes müssen somit zwei Merkmale erfüllt sein: Ein objektives äusseres, der Aufenthalt, sowie ein subjektives inneres, die Absicht dauernden Verbleibens (<ref-ruling> Erw. 3; ZAK 1990 S. 247 Erw. 3a; Eugen Bucher, Berner Kommentar, N 19 ff. zu <ref-law>). Nach der Rechtsprechung kommt es nicht auf den inneren Willen, sondern darauf an, auf welche Absicht die erkennbaren Umstände objektiv schliessen lassen (<ref-ruling> Erw. 2b, 119 II 65 Erw. 2b/bb, 97 II 3 Erw. 3).
3.- Das Verwaltungsgericht von Appenzell Ausserrhoden begründet seine örtliche Unzuständigkeit zur Behandlung der Beschwerde gegen den Einspracheentscheid der "Basler" vom 8. Juli 1999 im Wesentlichen damit, der Beschwerdeführer habe im Zeitpunkt des Verfügungserlasses als dem Kanton Appenzell Ausserrhoden zugewiesener Asylbewerber und Insasse einer Asylbewerberunterkunft noch keinen selbstständigen zivilrechtlichen Wohnsitz nach Art. 23 und Art. 26 ZGB begründet. Gleiches habe für den Zeitraum zu gelten, während welchem er als Saisonnier in der Schweiz geweilt habe, da ihm zwar die subjektive, nicht jedoch die auf objektiven und äusserlich wahrnehmbaren Kriterien beruhende Absicht dauernden Verbleibens attestiert werden könne. Somit käme nach <ref-law> als Gerichtsstand einzig der Wohnsitz des letzten schweizerischen Arbeitgebers in Frage, welcher nach den Akten im Kanton Graubünden gelegen habe.
4.- a) Dieser Auffassung kann nicht gefolgt werden. Bereits in <ref-ruling> hat das Bundesgericht den zivilrechtlichen Wohnsitz eines sich im Zeitpunkt der Verweigerung der Heiratsbewilligung 1 1/4 Jahre in der Schweiz aufhaltenden Asylbewerbers bejaht. Es erwog, der Aufenthalt des Gesuchstellers in der Schweiz sei nicht vorübergehend oder rein zufällig, sondern von einer gewissen Dauer gekennzeichnet. Zudem liessen die äusseren Umstände wie die Aufgabe des bisherigen Wohnsitzes im Ausland und die Einreichung des Asylgesuchs in klarer und für Dritte erkennbarer Weise den Willen erkennen, die Schweiz zum Mittelpunkt seiner Lebensinteressen zu machen. Entsprechend erachtete das Gericht die Voraussetzungen des <ref-law> als erfüllt. Daran ändere nichts, dass der Asylbewerber während der Dauer des Verfahrens in der Schweiz bloss toleriert sei, da im Falle der Abweisung des Asylgesuchs der fiktive Wohnsitz des <ref-law> greife, wonach der Aufenthaltsort als Wohnsitz gilt, wenn ein früher begründeter Wohnsitz aufgegeben und in der Schweiz kein neuer begründet worden ist (<ref-ruling> f. Erw. 2; Andreas Bucher, Der Personenstand der Asylbewerber, in: ZZW 53/1985 Nr. 12 S. 362; vgl. auch Kommentar zum Schweizerischen Privatrecht, Schweizerisches Zivilgesetzbuch I [Hrsg. Honsell/Vogt/Geiser], Basel 1996, Daniel Staehelin, N 19 zu <ref-law>). Es steht nichts entgegen, diese Rechtsprechung auch auf dem Gebiet des Bundessozialversicherungsrechts anzuwenden (vgl. Jürg Brechbühl, Die Rechtsstellung von Asylsuchenden und Flüchtlingen in den schweizerischen Sozialversicherungen, in: CHSS 1996 S. 144; Hanspeter Käser, Unterstellung und Beitragswesen in der obligatorischen AHV, 2. Aufl. 1996, N 1.22). Es trifft zwar zu, dass sich der Asylbewerber in dem Sinne in einer provisorischen Situation befindet, als er mit einem negativen Asylentscheid und der Wegweisung aus der Schweiz rechnen muss. Dies ändert aber nichts daran, dass er den Wohnsitz im Heimatland aufgegeben und die Schweiz zum Mittelpunkt seiner Lebensinteressen gemacht hat. Zudem ist der Aufenthalt auch auf (eine gewisse) Dauer ausgelegt, da sich das Verfahren bis zum rechtskräftigen Entscheid oder bis zur Wegweisung erfahrungsgemäss über einen längeren Zeitraum von bis zu einigen Jahren erstreckt (Andreas Bucher, a.a.O., S. 363), während dem er hier ein besonderes gesetzliches Aufenthaltsrecht (<ref-law>) geniesst. Im Übrigen ist die Situation des Asylbewerbers nicht mit derjenigen des Saisonniers vergleichbar, da dieser die Beziehungen zu seinem Heimatstaat in der Regel nicht abbricht, sondern einzig zu Erwerbszwecken in die Schweiz kommt und nach seiner befristeten Tätigkeit wieder (zu seinen Familienangehörigen) zurückkehrt. Schliesslich stünden einem allfälligen Wunsch nach Wohnsitzbegründung in der Schweiz öffentlich-rechtliche Hindernisse entgegen. Bei Saisonniers kann Wohnsitz in der Schweiz praxisgemäss erst angenommen werden, wenn sie sich mit der Absicht dauernden Verbleibens in der Schweiz aufhalten und die Voraussetzungen für die Umwandlung der Saisonbewilligung in eine ganzjährige Aufenthaltsbewilligung erfüllen oder zu erfüllen im Begriffe sind (<ref-ruling> Erw. 5b, 113 V 264 Erw. 2b mit Hinweisen).
b) Im vorliegenden Fall hat der Beschwerdeführer, welcher seit 1986 regelmässig als Saisonnier in der Schweiz
gearbeitet hat, am 9. Februar 1998 bei der Empfangsstelle K._ um Asyl nachgesucht. Damit hat er klar zum Ausdruck gebracht, seinen Lebensmittelpunkt in die Schweiz zu verlegen. Er hatte daher spätestens ab diesem Zeitpunkt Wohnsitz in der Schweiz. Daran würde im Übrigen auch ein abweisender Asylentscheid nichts ändern. Denn nach ständiger Rechtsprechung erfüllen auch vorläufig aufgenommene Ausländer im Sinne von Art. 14a ANAG das Erfordernis des schweizerischen Wohnsitzes (<ref-ruling> betreffend Internierung, welche durch das gleichartige Institut der "vorläufigen Aufnahme" ersetzt worden ist; nicht veröffentlichtes Urteil S. vom 23. Dezember 1999, I 115/97; Jürg Brechbühl, a.a.O., S. 144).
5.- Im Lichte des Gesagten hat die Vorinstanz ihre örtliche Zuständigkeit zu Unrecht verneint, nachdem der Beschwerdeführer im massgeblichen Zeitpunkt der Beschwerdeerhebung (vom 13. September 1999; vgl. Erw. 2 hievor) seinen Wohnsitz im Kanton Appenzell Ausserrhoden hatte.
6.- Im vorliegenden Fall beschränkt sich der Anfechtungsgegenstand auf die rein prozessrechtliche Frage nach der örtlichen Zuständigkeit, weshalb das Verfahren vor dem Eidgenössischen Versicherungsgericht kostenpflichtig ist (Art. 134 OG e contrario). Die Beschwerdegegnerin hat als unterliegende Partei die Gerichtskosten zu tragen (Art. 156 Abs. 1 in Verbindung mit Art. 135 OG). Dem Ausgang des letztinstanzlichen Verfahrens entsprechend steht dem Beschwerdeführer eine Parteientschädigung zu (Art. 159 Abs. 1 in Verbindung mit Art. 135 OG); damit wird sein Antrag auf Gewährung der unentgeltlichen Verbeiständung gegenstandslos.

Demnach erkennt das Eidg. Versicherungsgericht:
I. In Gutheissung der Verwaltungsgerichtsbeschwerde wird
der Entscheid des Verwaltungsgerichts von Appenzell
Ausserrhoden vom 8. Dezember 1999 aufgehoben und die
Sache an die Vorinstanz zurückgewiesen, damit sie,
nach Prüfung der weiteren Prozessvoraussetzungen, über
die Beschwerde gegen den Einspracheentscheid der Bas-
ler Versicherungs-Gesellschaft vom 8. Juli 1999 mate-
riell entscheide.
II. Die Gerichtskosten von Fr. 500.- werden der Basler
Versicherungs-Gesellschaft auferlegt.
III. Der geleistete Kostenvorschuss von Fr. 500.- wird dem
Beschwerdeführer zurückerstattet.
IV. Die Basler Versicherungs-Gesellschaft hat dem Be-
schwerdeführer für das Verfahren vor dem Eidgenössi-
schen Versicherungsgericht eine Parteientschädigung
von Fr. 2'500.- (einschliesslich Mehrwertsteuer) zu
bezahlen.
V. Dieses Urteil wird den Parteien, dem Verwaltungsge-
richt von Appenzell Ausserrhoden, dem Verwaltungsge-
richt des Kantons Graubünden und dem Bundesamt für
Sozialversicherung zugestellt.
Luzern, 19. April 2000
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der III. Kammer:
Die Gerichtsschreiberin: