From a practical standpoint, rather than a theoretical one, there are at least two pedagogically defensible ways to do this. Spiral curriculum, and Scaffolding
Use a Spiral Approach
I won't assume that you never mention variables early with this approach, but you just don't teach all that needs to be known at the first introduction of variables (or any other topic). To teach like this you mention things that need to be known deeply early on, partly to introduce terminology, but partly to permit simple uses in which deep knowledge isn't needed. Then, for example, variables but without reassignment could be used in setting up some sort of selection or iteration as your lecture focuses on those ideas rather than the variables. At any given point in time students know a little about a few things and a lot about some other things. Then, in the next cycle you go a bit deeper in some topics but also introduce, very lightly, other topics.
The implication is that a student never needs to completely understand any given topic the first time it is presented as it will be seen again. Everything is reviewed constantly in such a course.
For purposes of this particular question, a variable could be initialized somehow and then used within a selection structure. The student need only have the idea that the variable refers to a value and can be thought of as a temporary name for that value.
Teaching a course in a spiral way requires some pre-planning, of course. It isn't enough to put each important topic into the syllabus only once. Neither is it enough to expect that every student will get a lot out of the first introduction and you don't, therefore, need to obsess that everyone is on the same page before moving to the next topic.
An independent way of teaching is to have students first programming experiences done within a pre-defined richly endowed virtual world. The world is constructed so that interesting things can be done early without necessarily building up everything from the beginning. Often these world are simulations. For example, in Karel the Robot and its successors, programs consist first of writing sequences of statements to direct an existing robot. The robot's capabilities are built in and the student simply invokes existing functions/methods to achieve some complex effect. Next the student learns to write methods or functions as just abstractions over some sequence of such pre-build actions and other actions already built by the student. In this way it is functional abstraction that is the first real topic of importance. You can introduce variables or not, and you will certainly do so when you want several robots acting together. But these variables are just object references and little needs to be known about them, including whether they can be reassigned or not. Selection is certainly a reasonable topic in such a world, as is iteration, polymorphism, recursion, or whatever you need to teach.
However, careful thought needs to be given to the characteristics of the simulation world. How rich is the environment. It can be simple, for example, and still be Turing Complete.
Some teachers might choose this path with a single simulated virtual world, and others might choose to use several worlds of increasing sophistication and, perhaps, increasing complexity. I'll note that Greenfoot was built precisely to provide an environment in which such simulations and virtual worlds would be easy to build.
Both of these techniques are very powerful and have been used by many instructors over a long period of time. Of course, they may be combined to good effect.