Hardware stacks are a relatively recent feature (in historical terms) even though subroutine calls go way back. Many systems did subroutine calls by saving the return address in a register. On the IBM 1401, when you called a subroutine, the subroutine would actually modify the jump instruction at the end of the subroutine to jump back to the caller. Needless to say, this wouldn't work with recursion. On the PDP-8, a jump to subroutine would automatically store the return address in the first word of the subroutine.
On many systems, if you wanted a stack, you had to implement it in software. For instance, on the Xerox Alto (1973), when you called a subroutine, the subroutine would then call a library routine that would save the return address and set up a stack frame. You'd call another library routine to return from the subroutine and it would pop stuff from the stack.
The 8008, Intel's first 8-bit microprocessor, had an 8-level subroutine stack inside the chip. There were no push or pop instructions.
I don't have direct experience, but I believe that system/360 programs have historically not had stacks, opting instead for a statically allocated 'program save area'.
RISC-type architectures with a branch-and-link instruction (as opposed to a jsr- or call-type instruction) generally have a stack by convention only, because the CPU doesn't need one to operate. (For handling interrupts and exceptions there is usually some other mechanism for storing the old program counter.)
From the perspective of "stack" as an underlying computation structure: Have you ever played a Nintendo game? You've used a program that did not involve a stack. The matter of "stack" gets really fuzzy in Haskell, too; it certainly has something like one because there are functions, but the way the laziness gets resolved makes it quite substantially different from the way a C program's stack works.
If a time traveler from a century in the future came back and told me that their programming languages aren't anywhere as fundamentally based on stacks as ours are, I wouldn't be that surprised. I'm not sure any current AI technology (deep learning, etc.) is stack-based.
From the perspective of "stack" as in "stack vs. heap", there's a lot of existing languages where at the language level, there is no such distinction. The dynamic scripting language interpreters put everything in the heap. The underlying C-based VM may be stack based, but the language itself is not. The specification of Go actually never mentions stack vs. heap; all the values just exist. There is a stack and a heap like C, but what goes where is an implementation detail handled by the compiler, not like in C where it is explicit.
To some extent, I think the replies to my post actually demonstrate my point to a great degree. People's conceptions of "how a computer works" are really bent around the C model... but that is not "how a computer works". Computers do not care if you allocate all variables globally and use "goto" to jump between various bits of code. Thousands if not millions of programs have been written that way, and continue to be written in the embedded arena. In fact, at the very bottom-most level (machines with single-digit kilobytes), this is not just an option, but best practice. Computers do not care if you hop around like crazy as you unwind a lazy evaluation. Computers do not care if all the CPU does is ship a program to the GPU and its radically different paradigm. Computers do not care if they are evaluating a neural net or some other AI paradigm that has no recognizable equivalent to any human programming language. If you put an opcode or specialized hardware into something that really does directly evaluate a neural net without any C code in sight, the electronics do not explode. FPGAs do not explode if you do not implement a stack.
C is not how computers work.
It is a particular useful local optimum, but nowadays a lot of that use isn't because "it's how everything works" but because it's a highly supported and polished paradigm used for decades that has a lot of tooling and utility behind it. But understanding C won't give you much insight into a modern processor, a GPU, modern AI, FPGAs, Haskell, Rust, and numerous other things. Because learning languages is generally good regardless, yes, learning C and then Rust will mean you learn Rust faster than just starting from Rust. Learn lots of languages. But there's a lot of ways in which you could equally start from Javascript and learn Rust; many of the concepts may shock the JS developer, but many of the concepts in Rust that the JS programmer just goes "Oh, good, that feature is different but still there" will shock the C developer.
On many systems, if you wanted a stack, you had to implement it in software. For instance, on the Xerox Alto (1973), when you called a subroutine, the subroutine would then call a library routine that would save the return address and set up a stack frame. You'd call another library routine to return from the subroutine and it would pop stuff from the stack.
The 8008, Intel's first 8-bit microprocessor, had an 8-level subroutine stack inside the chip. There were no push or pop instructions.