You shouldn't have to rewrite the Arduino Due bootloader - you just need to write a program that can act as USB HID using the native USB port, and upload the program to the Arduino Due. You can use the Due's programming USB port to do the upload.
But here's info on the Arduino Due boot process:
The Due has a ROM bootloader that listens to the USB native port and Serial port 0. You can talk to the ROM bootloader via USB directly by resetting the SAM3X8E and using the native port. But I've not found that method to be very reliable. The more frequently used programming port is connected to an Atmel AVR 16U2 microprocessor acting as a USB-serial converter, connected to the SAM3X8E serial port 0. The Arduino 1.5 IDE can talk to the 16U2 using the Bossa command (bossac), reset the SAM3X8E, and upload new programs to it it. This page explains the Arduino Due's bootloader in detail.
If you're interested, here's the source code for the 16U2 AVR USB-serial converter.
And here's Bossa - the Due's command that corresponds to avrdude.
Using bossac (the Bossa commandline tool), you can upload code the SAM3X8E, using the builtin ROM bootloader.
On creating HID devices:
Here's a link to an Atmel application note that has example code for creating a program that can act as a USB HID keyboard:
http://asf.atmel.com/docs/latest/common.services.usb.class.hid.device.keyboard.example.sam3x_ek/html/index.html
The source code to this example is the in the Atmel ASF packages - unfortunately, a large download. Here's where to get it:
http://asf.atmel.com/docs/latest/download.html
Once you download it, the source code the HID keyboard example is in this folder:
common/services/usb/class/hid/device/kbd/example/sam3x8e_arduino_due_x
Here's a list of the other app notes, with examples of other kinds of USB and HID devices. Look for the ones that are for the Arduino Due:
http://asf.atmel.com/docs/latest/applications.html
Diagram of Loading Process
It doesn't sound like you read very far into the datasheet. From page A-4:
Preloader
The function of the preloader is user-defined. However, typical functions include
initializing the SDRAM interface and configuring the HPS I/O pins. Initializing the
SDRAM allows the preloader to load the next stage of the boot software (that might
not fit in the 60 kilobytes (KB) available in the on-chip RAM). A typical next software
stage is the open source boot loader, U-boot. The preloader is allowed to load the next stage boot software from any device
available to the HPS. Typical sources include the same flash device that contains the
preloader, a different flash device, or a communication interface such as an EMAC.
This is from the datasheet pcj50 linked.
Best Answer
The bootloader lets you reprogram the PIC from the USB port, taking advantage of the ability of the controller to write into its own program memory. Usually, it checks to see if some criteria is met, like some bit being set high, before entering the programming mode. It will shift your program into higher memory space to accommodate the boot loading protocol at the normal start vector.
This is the way to go if you see a need for something like an end-user updating the firmware on your device without special programming hardware.
Serial port boot loaders are a bit easier to learn, as you don't have to deal with the USB stack.