The discussion here hits at a core part of the theory of computing. To address the question, it's worth discussing at a high level three classes of computing machines.
The simplest is finite state automata (FSA), which have no memory, and accept/reject inputs by following a predefined set of steps to pattern match. Typically these are realized as regular expressions.
The second class of machines are push-down automata (PDA). They have a stack memory and can only manipulate the item on the top of the stack by pushing a new item on top of the stack or throwing the top item on the stack away. These are often used, for example, for parsing context free grammars. Push down automata are more powerful in the types of solutions you can build than finite state automata (effectively, every FSA is a PDA without a stack).
The third class of machines are Turing machines (TM). They are typically modeled using a tape-based memory, but conceptually you can think of it as a random access memory where you can update any spot of in the memory in response to some state change. These are the most powerful type of computing model and is strictly more powerful than a PDA (a PDA is essentially a Turing machine where you can only write to the end of the tape or remove what's at the end).
So what does this have to do with our discussion of variables? Well, if you really have no storage in your app, you can effectively only create programs as powerful as DFAs. If you only had a stack (say, by using recursive procedures), then you can model programs as powerful as PDAs. Once you introduce at least one variable, you can build as complex a program as one can model with any TM.
Of course, you can't really build an App Inventor app without some form of memory (the Screen serves as one and must manage app lifecycle states). Internally, each component instance (Screen1, Button1, etc.) creates a new variable that is effectively constant (you can't replace Button1 with a different button at runtime). These objects have some internal state (variables) that you can manipulate via their properties. Most people differentiate a variable (not owned by any particular object) and a field (owned by a specific object). While it's an implementation detail, variables at the blocks level are implemented as fields on the Screen, so as you can see the line between the concepts is somewhat fluid.
