Sachverhalt: A. A._ (geb. 1961) stammt aus den Kapverden. Er reiste 1979 in die Schweiz und verfügte seit 1984 über eine Niederlassungsbewilligung. Er befand er sich seit 2010 in Untersuchungshaft und ab dem 4. Juni 2012 im (vorzeitigen) Strafvollzug. Am 8. Mai 2012 wurde er wegen verschiedener Delikte im Zusammenhang mit massiver häuslicher Gewalt zu einer Freiheitsstrafe von 9 Jahren verurteilt. Das Appellationsgericht des Kantons Basel-Stadt bestätigte das erstinstanzliche Urteil am 26. November 2014 im Schuldpunkt und reduzierte das Strafmass auf 7 1⁄2 Jahre Freiheitsstrafe. Gegen dieses Urteil gelangte A._ mit derzeit noch hängiger Beschwerde ans Bundesgericht (Verfahren 6B_304/2015). Mit Verfügung vom 23. März 2015 verfügte die Statthalterin am Appellationsgericht des Kantons Basel-Stadt die Entlassung von A._ aus dem vorzeitigen Strafvollzug zu Handen des Migrationsamts. B. Bereits am 24. September 2012 hatte das Migrationsamt des Kantons Basel-Stadt die Niederlassungsbewilligung von A._ widerrufen und ihn aus der Schweiz weggewiesen mit der Anordnung, das Land nach der Entlassung aus dem Strafvollzug umgehend zu verlassen. Am 24. März 2015 ordnete das Migrationsamt des Kantons Basel-Stadt gegen A._ Ausschaffungshaft bis zum 23. Juni 2015 an. Mit Urteil vom 25. März 2015 entschied der Einzelrichter für Zwangsmassnahmen im Ausländerrecht am Appellationsgericht als Verwaltungsgericht, die angeordnete Ausschaffungshaft sei rechtmässig. Gleichzeitig wies der Einzelrichter auch ein gegen ihn erhobenes Ausstandsgesuch ab. C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 24. April 2015 beantragt A._ dem Bundesgericht, das Urteil des Einzelrichters für Zwangsmassnahmen vom 25. März 2015 sei aufzuheben und er sei aus der Ausschaffungshaft zu entlassen. Eventuell sei die Streitsache zur Neubeurteilung durch einen verfassungsmässigen und unabhängigen Richter an die Vorinstanz zurückzuweisen. Im Weitern ersucht der Beschwerdeführer um unentgeltliche Rechtspflege und Verbeiständung. Die Vorinstanzen schliessen auf Abweisung der Beschwerde.