Faits : A. Le 3 mai 2016, A._ a requis son inscription au tableau public des avocats des Etats membres de l'Union européenne auprès de l'Autorité cantonale de surveillance des avocats du canton du Valais. A l'appui de sa requête, l'intéressé a produit une attestation intitulée " Certificate of Good Standing " établie le 15 avril 2016 par la " Solicitors Regulation Authority " (ci-après: la SRA), autorité indépendante de réglementation des avocats en Angleterre et au Pays de Galles, d'où il ressortait que A._ avait obtenu le titre de " solicitor " le 3 septembre 2001. Ce document précisait que l'intéressé, qui n'avait été ni suspendu ni radié, ne détenait pas de certificat lui octroyant le droit d'exercer (" [h]e does not hold a current practising certificate "), de sorte qu'il n'était pas autorisé à pratiquer en Angleterre et dans le Pays de Galles (" [h]e is not currently entitled to practise as a solicitor of England and Wales "). Il était en outre indiqué que A._ avait sollicité un certificat l'autorisant à exercer mais que cette demande avait été rejetée par la SRA. Une procédure d'appel était en cours. B. Par décision du 20 mai 2016, le Président de l'Autorité cantonale de surveillance des avocats a rejeté la requête de l'intéressé. Il a considéré que A._ n'avait pas établi être habilité à exercer dans son Etat de provenance une activité d' " Advocate ", de " Barrister " ou de " Solicitor ". A l'encontre de cette décision, A._ a formé un recours auprès de la Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) qui l'a rejeté par arrêt du 1er septembre 2016. C. A._ forme un recours en matière de droit public au Tribunal fédéral, subsidiairement un " recours de droit constitutionnel ". Outre l'assistance judiciaire, il conclut, avec suite de frais et dépens, à l'annulation de l'arrêt du 1er septembre 2016 et au renvoi de la cause à l'autorité précédente pour nouvelle décision dans le sens des considérants. Subsidiairement, il requiert la réforme de l'arrêt entrepris en ce sens que l'arrêt de la Cour de céans vaudra inscription de l'intéressé sur la liste publique des avocats du canton du Valais à compter du 27 avril 2016. A._ demande en outre au Tribunal fédéral de poser des questions préjudicielles à la Cour de Justice de l'Union européenne (CJUE) concernant l'interprétation et l'application de l'art. 3 de sa directive 98/5/CE. Le 21 septembre 2016, le Tribunal fédéral a renoncé provisoirement à demander une avance de frais et informé l'intéressé qu'il sera statué ultérieurement sur sa demande d'assistance judiciaire. Le Tribunal cantonal et l'Autorité cantonale de surveillance des avocats ont renoncé à se déterminer sur le recours. L'Office fédéral de la justice n'a pas déposé d'observations. Le 4 octobre 2016, le recourant a produit une nouvelle pièce.