In Raúl Rojas' paper on the Z1/Z3(1), he writes that "instead of using gears (as Babbage had done in the previous century), Zuse implemented logical and arithmetical operations using sliding metallic rods. The rods could move in only one of two directions (forward or backward) and therefore were appropriate for a binary machine." The Z1 is 1936-38.
This doesn't quite explain if rods or binary arithmetic came first, but there is a footnote to Zuse's book "Der Computer mein Lebenswerk".
As a side note, I can recommend seeing the Z1 in the Technical Museum in Berlin if you are near.
Jesper Juul