Other possibilities include:
Running the Atmega328p at 8MHz and powering at 3.3v. Both devices would be operating within spec.
Running the whole system at 3.3v but without changing the clock on the '328. The advantage here is you'll get the full throughput from the '328, assuming you need it. The disadvantage (assuming a 16MHz Atmega328p) is that it will be running out of spec (overclocked) but they seem to be conservatively enough speced that most chips do fine. I have built two boards this way for the same reason: to put both a 328p and an ESP8226-01 on one board. I ran some rather rudimentary tests on the Atmega chips I put on those boards to find out if they would work at that voltage. I didn't see any issues and I haven't discovered any since.
Would it be possible to run the ATmega at 8 MHz using a 16 MHz
external oscillator by simply uploading a new sketch?
It may be possible to use its internal resonator and ignore the connected crystal; I haven't tried this. Could you clip off the external crystal if you needed to?
This article talks about setting the fuses that control the clock frequency. One thing to keep in mind is you'll need to replace the bootloader with one appropriate for the new clock frequency. You may find an 8Mz bootloader ready to upload, or recompile it yourself from source. Optiboot is a good choice: open source, has a small footprint, and you can set its upload baud-rate. You can upload a new bootloader using another Arduino as an ISP programmer - there are lots of articles about doing this and the code for the Arduino-as-programmer is one of the Arduino IDE example-programs.