Should I try to connect the usb at the same time (to provide another power source for the chip while programming it)?
No, only one power source at a time. You can turn the "Target Power" OFF (JP3 jumper pulled) on the USBtiny and power it from the USB, but I suspect the same results.
Do you get any activity on the Rx/Tx LEDs?
Another longshot is turning the clock down on the USBtinyISP with a -B 32 in the command line.
avrdude -p at90usb82 -B 32 -P usb -c usbtiny -U flash:w:UNO-dfu_and_usbserial_combined.hex -U lfuse:w:0xFF:m -U hfuse:w:0xD9:m -U efuse:w:0xF4:m -U lock:w:0x0F:m