Some of the devices in the Mega AVR line support external memory. The ATmega640 is an example. Generally you'll only find it on higher pin-count devices which aren't available in DIP packages. If you need something that's a bit easier to work with, the Teensy 2.0++ is an option.
As for your Z80 computer, another option would be to add some simple bank-switching hardware to allow you to boot from ROM. Probably more work and less flexible than just using an AVR for boot though.
I'm fine working with surface-mount stuff, I can solder it by hand, it's not actually as hard as it looks. Bank switching seems like a pain to manage though.
I wish I had learned this stuff in school. I majored in CS, and we didn't go any lower level than C++.
As for your Z80 computer, another option would be to add some simple bank-switching hardware to allow you to boot from ROM. Probably more work and less flexible than just using an AVR for boot though.