If you look at history, there were Russian/Soviet bases on German soil in the recent past. While Germany was divided into the FRG and the GDR, there was the Group of Soviet Forces in Germany in East Germany. The repatriation of these forces was still ongoing during the German Reunification and the dissolution of the Soviet Union, which made them Russian bases on FRG territory.
Allowing new Russian bases could be considered as a breach of EU and NATO agreements, but leaving those is a theoretical option. The Treaty on the Final Settlement with Respect to Germany explicitly allows Germany to select a military alliance.
One might argue that the 1994 deadline for the withdrawal of the Soviet forces (Article 4) constitutes a ban on any new bases, but that would be stretching things.