Well, how much say do we have over the architecture? Paging/banking hardware is pretty common on 6502-based systems. Such hardware decouples the virtual address space (what the CPU sees) from the physical address space. Typically they are used to extend memory space (e.g. the Apple //e's 80-column card) but they can also be used as a mass indirection mechanism (e.g. the NES's various "mappers", which granted are used more by its graphics coprocessor). The act of paging is "instantaneous" since you are just setting a hardware register.
So if you are designing the hardware, give it an extra 4 KiB or so (16 pages), mapped through a paging circuit to the zero page. On entry to a function, increment the current page; on exit, decrement. Now you have a way to push all "local variables" that is faster than even pushing all the registers. You could even get fancy and XOR bits 7-4 of the page register with bits 4-7 of the paged address lines, so the compiler can choose anywhere from 16 256-byte frames up to 256 16-byte frames.
There's also the Apple ///'s approach to almost-transparent banking on a 6502. The hardware could redirect the zero page to (almost) anywhere in the 64K address space (foreshadowing the 65C816's movable zero page), and it maintained a sort of second zero page called the "X" page at a fixed offset from the zero page. Then on any indirect access to memory through the zero page, it would check the corresponding byte in the "X" page and if it was valid it would use it as additional address bits. As implemented in the ///, programs could thus directly access up to 512KB without doing any traditional banking or paging.
Of course, it was also possible to do traditional banking on the /// so that program code could reside anywhere in the 512K, but I thought the X page thing was pretty neat when I finally figured it out.
Great tidbits! I'm reminded also of the 6809's movable "zero" page (the "direct page"), though it has a 16-bit stack register so the trick isn't really necessary.
So if you are designing the hardware, give it an extra 4 KiB or so (16 pages), mapped through a paging circuit to the zero page. On entry to a function, increment the current page; on exit, decrement. Now you have a way to push all "local variables" that is faster than even pushing all the registers. You could even get fancy and XOR bits 7-4 of the page register with bits 4-7 of the paged address lines, so the compiler can choose anywhere from 16 256-byte frames up to 256 16-byte frames.