I ran into the following error with a recent Arduino IDE version (1.8.9) when trying to upload to an "Arduino Nano" clone (ATmega328P):
avrdude: stk500_recv(): programmer is not responding
avrdude: stk500_getsync() attempt 1 of 10: not in sync: resp=0x18
...
avrdude: stk500_recv(): programmer is not responding
avrdude: stk500_getsync() attempt 10 of 10: not in sync: resp=0x18
Problem uploading to board. See http://www.arduino.cc/en/Guide/Troubleshooting#upload for suggestions.
The problem could be resolved by choosing "ATmega328P (Old Bootloader)" as Processor in the Tool menu - as now suggested to me and solved in Arduino Nano uploading gives error: avrdude: stk500_recv(): programmer is not responding.
The change was made in August 2018 with the release of Arduino IDE 1.8.6: https://github.com/arduino/Arduino/releases/tag/1.8.6
Details about the different bootloaders are described in Arduino Nano ATmega328P bootloader difference.
It seems the fuses have to be changed in order to make full use of the newer, smaller bootloader, so an ISP will have to be used anyway.
But is the bootloader able to update itself (via Tools > Burn bootloader) or is there an intermediate "bootloader update sketch" available?