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.