According to law, the perpetrator will be expeled from Germany after serving his sentence, but not before it ends.
While this describes common practice, it seems it is not outside the competence of the minister of justice to order that an expulsion should take precedence over serving the sentence in full.
A pardon is possible if the Federal President decides so personally and for the individual case.
The expulsion of foreign citizens because of crimes commited is common practice in Germany. § 54 Aufenthaltsgesetz (residence law) defines a "grave particular interest" for expeling a person in cases of long prison sentences and crimes against life, among others:
(1) Das Ausweisungsinteresse im Sinne von § 53 Absatz 1 wiegt besonders schwer, wenn der Ausländer
- wegen einer oder mehrerer vorsätzlicher Straftaten rechtskräftig zu einer Freiheits- oder Jugendstrafe von mindestens zwei Jahren verurteilt worden ist oder bei der letzten rechtskräftigen Verurteilung Sicherungsverwahrung angeordnet worden ist,
1a. rechtskräftig zu einer Freiheits- oder Jugendstrafe von mindestens einem Jahr verurteilt worden ist wegen einer oder mehrerer vorsätzlicher Straftaten
a) gegen das Leben,
...
After such an expulsion, the person can be banned from re-entry into Germany for up to 20 years.
These expulsions can be ordered even instead of serving a prison sentence, or before it ends. Serving the sentence can restart if the perpetrator re-enters the country. § 456a Strafprozessordnung (code of criminal procedure) ascertains:
(1) Die Vollstreckungsbehörde kann von der Vollstreckung einer Freiheitsstrafe, einer Ersatzfreiheitsstrafe oder einer Maßregel der Besserung und Sicherung absehen, wenn der Verurteilte...aus dem Geltungsbereich dieses Bundesgesetzes abgeschoben, zurückgeschoben oder zurückgewiesen wird.
(2) Kehrt der Verurteilte zurück, so kann die Vollstreckung nachgeholt werden...
In practice, there are further rules followed. While they differ from Land to Land, their core stipulations seem to be the same everywhere. As an example, the decree by the Brandenburg minister of justice first remarks that "there should not be the impression that the state does not take measures after crimes were committed by foreign citizens":
Bei der Anwendung des § 456 a StPO ist aber darauf zu achten, daß das allgemeine Ziel des Strafrechts nicht in unvertretbarer Weise beeinträchtigt wird und daß der durch § 456 a StPO ermöglichte Verzicht auf den weiteren Strafvollstreckungsanspruch des Staates nicht zu dem Eindruck führt, daß der Staat aus Straftaten ausländischer Staatsbürger und den aus ihnen resultierenden Gerichtsurteilen keine Konsequenzen mehr zieht.
As a general rule, at least half of a timed prison sentence should be served. In cases of very serious crimes, the period should be longer:
Eine über den Halbstrafenzeitpunkt hinausgehende Vollstreckung kommt dann in Betracht, wenn aus besonderen in der Tat oder in der Person des Verurteilten liegenden Gründen oder zur Verteidigung der Rechtsordnung eine nachhaltige Vollstreckung geboten ist. Dies gilt insbesondere
- bei Verurteilungen wegen besonders schwerwiegender Delikte,
- ...
But for life sentences as in the case of Vadim Krasikov, an exemption from serving the full time can only be ordered after fifteen years. Even more, because the court stated the "particular graveness of the crime" in his case, the exemption is excluded:
Bei lebenslanger Freiheitsstrafe kommt ein Absehen von der weiteren Vollstreckung nicht vor Verbüßung von 15 Jahren in Betracht.
Eine Maßnahme gemäß § 456 a StPO kommt nicht in Betracht, wenn das Gericht die besondere Schwere der Schuld des Verurteilten festgestellt hat.
Edit: These rules are set by a decree in which the minister of justice instructs the prosecutors (which act as law enforcement authority) how to intepret § 456 a StPO. Prosecutors are bound to follow these instructions, and the minister, in principle, is free to instruct in a different way. I am not completely sure if the minister could simply order to deviate from the decree in a single case, of if he had to issue a change, but the result is the same: it seems to be within his competence to order that an expulsion takes precedence over serving a sentence.
A pardon would also be possible. Normally, in cases of murder the right to pardon is granted to the head of the Land the court that heard the case is located in, in this case the governing mayor of Berlin. But as the court stated the involvement of a foreign secret agency, the prosecution was lead by the federal Public Prosecutor General (§ 120 Gerichtsverfahrensgesetz). This gives the sole competence to the federal president. While he may delegate that right to others in general, for cases of "extraordinary relevance", he has reserved the right explicitely for himself.
According to an analysis by the scientific service of the federal parliament, pardons always need to be a decision in a singular case, and are at the free discretion of the president. Federal ministers "prepare pardon cases that are in their area of responsibility". Pardons also cannot be reviewed by a court.
