A stored-program computer requires the program itself to be stored in electronic memory, the Z3 uses electronic memory for input and output but tape for the program.
IMO Zuse's machines were the big deal, but they were buried under a number of other firsts that weren't that revolutionary, after the war when the Allies were writing history alone for a few years.
While I agree that, conceptually, there is little difference between a program on tape and one in working memory, the latter has a huge speed advantage. More intriguingly, I believe it was thought at the time that the ability of a program to modify itself would be very useful. Turing had already shown that it did not expand what is computable (though I do not know if that was widely appreciated), but even so, when you have very little, and slow, working memory, if it allowed you to reduce the size or speed of your program, that might be a big deal. Even the early COBOL allowed for limited self-modification, in the form of a goto that could be modified during execution to go to different addresses. The problem with self-modifying code turned out to be that it is very hard to reason about and debug.
British machinery like Colossus was still kept a closely guarded secret until the mid 1970s.
Instruction pointer and explicit branching.
The Z3 is still (in a theoretical sense) Turing-complete, even without branching instructions (exponential path construction).
"We can therefore say that, from an abstract theoretical perspective, the computing model of the Z3 is equivalent to the computing model of today's computers. From a practical perspective, and in the way the Z3 was really programmed, it was not equivalent to modern computers."