…what are the consequences? Are there any other viable options for staging operations in the Middle East? Would Germany need to leave NATO to do it? France kept it’s membership after it kicked out foreign military bases.
First of all, this scenario is unlikely. The events in the past few years were rather the opposite: American (and now British) military bureaucracies closing down bases in Germany (or planning to do so), and German politicians lobbying for them to stay - a military base with its personnel and needs in terms of supply is a huge boost for the economy of the surrounding region.
To answer the question: There are other countries that would very much like to step in. Several countries in Eastern Europe, like Poland or Hungary, have been proposed as alternative sites for U.S. bases, and while I don’t know if there are still concorete plans to do so, they would certainly be envisgaed as alternatives if Germany closed down the bases there. For Middle East operations, I guess Turkey would be a good choice, too.
Germany would not have to leave NATO to do that, btw. The legal basis for the presence of U.S. troops in Germany is not the NATO Treaty itself, but special status of forces agreements concluded on top of the NATO Treaty. Germany could suspend or terminate these agreements while still remaining a NATO member.