First I tried the simple way, flashing a ATMega8U2 but the attempt to solder hair-thin wires to the QFN package of the 8U2 failed
Are you saying that your board does not have the ICSP header? If not why not? That's the obvious way to program the 8U2/16U2.
If the U2 is not on the board where is it? Have you made a programming dongle like the Taij people have? If so see my previous paragraph
The SAM also has a USB bootloaders loaded into the silicon, you can program it using the native USB port if you manually press the erase button first.