Provided that you are okay with producing a customized PC side tool (which you would probably want anyway for user convenience) automated target selection should be far superior to manual.
You should be able to use one ATmega16u2 with a minimally customized firmware as a front end to program two distinct ATmega328p's. This could be as simple as selecting the target based on the baud rate, having it hold the de-selected one in reset the whole time, and using some resistors on the shared TX lines for safety. Last I checked the stock firmware used a soft serial at some rates, and that can be put on different pins, so it could be another way to de-conflict and select targets.
Your idea of using a 32u4 both as a functional part and as a buddy-programmer for another part is perfectly valid too - you can do that programming to a serial bootloader (it should be a simple matter to port the 16u2 firmware, or find another example), or via the ISP pins.