There is more or less no "quickest way".
You anyhow will need to (1) apply for national visa (which will be processed by both embassy and immigration office, i.e. Ausländerbehörde), (2) enter Germany on that visa and start working, and (3) then apply for residence permit (e.g., Blue Card).
Answering other questions of yours:
up to 3 months to get ...
I had the same question and emailed Bundesagentur für Arbeit (BA). In my case, the officer said that, with the internship
less than 90 days within 12 months, and
during my study after 4th semester in H+ institution
there is no need for BA's 'Einvernehmen' because it is not considered an employment (BeschV § 30 Nr. 2;...