Start simple. If you're just replacing a "(NO) VACANCY" sign, you do NOT need a full matrix grid, and you do NOT need any shift registers! Just wire up two independent LED circuits.
One circuit controls all of the LEDs in the pattern for "NO".
The other circuit controls all of the LEDs in the pattern for "VACANCY".
You don't even need a microcontroller-- two toggle switches will activate/deactivate the necessary driving transistors of the above circuits. Total parts cost probably under US$50 including the AC-DC adapter (find a computer repair/recycling shop, they always have bins and bins of random DC supplies for almost free)
This way you can utilize your space and LEDs more efficiently. A 8x80 matrix that only displays "VACANCY" will have about 50% of the LEDs that simply are never utilized because they represent black parts of the text. Basically I'm suggesting that you use LED ribbons to mimic the neon you're replacing. Less control-ability, but it will be brighter because you're not scanning the display (8 row display will have 1/8 duty cycle)
Obviously if you want to display other text, you'll have to go for the multipurpose 8x80 matrix and all the multiplexing that manages it.
Very good suggestions. I believe I will go this route for the No Vacancy portion. What kinds of RF devices are there for doing wireless control. I know of the XBee and how it can be setup to work without an Arduino or other microcontroller, but the XBee may be just a bit too much for a simple on/off. Actually, I wonder if I could take apart and use the RF system of an RC car.