Since I like the last approach the best, I'll try to expand upon the idea:
Suppose you have a PROM and the first couple of instructions look like this:
ORG 0x0000 ; this is what the CPU thinks it sees
JMP Start ; at address 0x0000 a 3 byte jump to 0x8003 in 8080 talk this is C3 03 80
; note that this instruction also exists at 0x8000
ORG 0x8000
JMP Start ; this is the exact same instruction that is ORG'd at 0x0000 C3 03 80
Start: ; at address 0x8003 is the first instruction of the monitor
... < this is the starting point for the monitor.
When you create the PROM, ignore the stuff at 0x0000 and just assemble and burn the code that starts at 0x8000. That JMP instruction works from either address since it is a direct jump to an address.
Now, the address decoding for the PROM is to normally involve the high address bit (or some combination of bits) so you need to include the output of a D-flop that is automatically reset at startup (or by a reset signal/switch). Simultaneously, you need to include the output of the flop into the CE' logic for the RAM. Bottom line, when the D-flop is cleared at reset, the RAM disappears and the PROM shows up at both 0x0000 and 0x8000. When the flop is set, RAM shows up at low addresses and the PROM still shows up at 0x8000.
Now, after the JMP Start instruction following reset, your CPU will be headed off to 0x8003 (assuming 3 byte JMP instruction like the 8080). The PROM is ALWAYS mapped into 0x8000 so the state of the D-flop is irrelevant.
Finally, now that we have actually entered the PROM at 0x8003, we need some way to set the D-flop to enable RAM and disable the mapping of the PROM at 0x0000. One way to do this is to notice MEMRD' with the high bit of the address = '1'. We always SET the flop so the D input should be a solid '1'. The only thing that resets the flop is the reset signal. This will come from the RESET toggle switch and/or a capacitor on the R input. Whatever it takes to guarantee the flop is reset at startup.
Short answer, the PROM shows up at 0x0000 long enough to JMP to 0x8003 and gets mapped out of low memory as soon as the first byte is read at 0x8xxx.
ETA: This approach assumes that the CPU will cleanly start at 0x0000 (pretty easy to force a reset on the PC) and that MEMRD' is clean at startup so the D flop doesn't get set prematurely. The advantage to this approach is that it doesn't play convoluted tricks with the address signals (inverting and such) that ultimately need to be unwound.
ETA: That JMP Start instruction will only be executed at 0x0000, never at 0x8000 because we have already jumped over it and are working at 0x8003. Looks strange but it works. Make sure to comment it because it looks like a stupid instruction. Why JMP to the next sequential address? Yup! I can simplify that code right out of here! Something like that...