I wrote an SD card bootloader for the TI MSP430 microcontrollers. The user would insert an SD card with the new firmware on it, then power up. The bootloader would detect the presence of the card, read in the latest file of the correct size, and flash the contents to the chip. I found that I could make this work without dealing at all with the FAT since files would naturally be stored in sequential sectors. But this was written in MSP430 assembler, so it probably wouldn't do you much good except to follow the logic, but you're welcome to whatever might be useful.
https://github.com/gbhug5a/SD-Card-Bootloader-for-MSP430I think you would find that a microSD holder is *VERY* inexpensive, and if you can run your AVR at 3.3V, there would be very few additional parts needed. And I think you can still find 256MB, 512MB or 1GB microSD cards for a buck or two to include with the device.
You might be able to find an SD card bootloader for AVR. There appear to be three of them on Github.
This would be easiest for the user because he doesn't need drivers or softwear installed, and doesn't even need a particular operating system. The downside for you is the need to write the bootloader, and the need to provide power to the SD card, which is often a lot more than the entire rest of the project.