Uploading/Flashing different programs to two different Arduino uCs, using one USB
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. 

Now that I think about it, there's been a version of this question here before, as I remember writing about an idea for using two ATmega328p's permanently wired to a stock USB-serial, but with their bootloaders customized to use unique baud rates, and a little logic added so that on reset each would leave its serial TX pin tristated if it didn't detect bootloader traffic at its individually unique baudrate, thus allowing the other to be programmed without interference.