Solución 1:
gdisk tiene una opción para ello. Abra las opciones extendidas, elija 'zap':
gdisk /dev/sda
> x
> z
> w (maybe?)
Solución 2:
Esto debería hacerlo de manera bastante eficiente, según la información sobre GPT en este sitio.
Borre el primer bloque (dos sectores de 512 bytes para MBR y encabezado, y 16 KiB para entradas de partición):
dd if=/dev/zero of=/dev/sdwhatever bs=512 count=34
La última parte es más complicada. Tomo prestado de esta pregunta para ayudar, aunque si tiene drescue a mano, puede ir a la inversa.
dd if=/dev/zero of=/dev/sdwhatever bs=512 count=34 seek=$((`blockdev --getsz /dev/sda` - 34))