How to restore a deleted HFS+ partition table

I have an external 2TB hard drive with one HFS+ partition, and accidentally dd'ed over the first ~500 MB of it. I have carelessly placed some new partitions in an attempt to repair it, because I had an online backup in case things went south. The backup fell through, though, and I have to recover the data from this drive now. The readable data in the partition table is most likely unusable or misleading.

I have tried running Testdisk and placing the partition using pdisk and this guide, without success. I don't know anything about the partitioning before the accidental dd except that I selected the standard options for HFS+ from Disk Utility for it and used all the space on the drive.

Is there a way to simply format the drive as a single HFS+ partition again, without losing all the data? How does HFS+ store its files and metadata, and will it be possible to recover the data this way?

Here is the log of what happened from the shell log:

$ diskutil list
[...]
/dev/disk2
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *2.0 TB     disk2
   1:                  Apple_HFS WD-40                   2.0 TB     disk2s1

$ diskutil unmountDisk /dev/disk2
Unmount of all volumes on disk2 was successful

$ sudo dd if=/Users/Felix/Downloads/xubuntu-12.04.3-alternate-i386.img of=/dev/disk2 bs=1m
^C503+0 records in
502+0 records out
526385152 bytes transferred in 16.409358 secs (32078351 bytes/sec)
$ diskutil list
[...]
/dev/disk2
   #:                       TYPE NAME                    SIZE       IDENTIFIER
   0:     FDisk_partition_scheme                        *2.0 TB     disk2
   1:                       0x17                         715.1 MB   disk2s1

And the log from the Testdisk scan (Deeper Search), which I aborted at around 40% progress because the drive is so large:

[...]
LVM magic value at 31676/178/3

LVM magic value at 31685/19/35
Search for partition aborted

Results
     MS Data                354087269  354093442       6174
     NTFS found using backup sector, blocksize=512, 3161 KB / 3087 KiB
     MS Data                354093442  354099615       6174 [Boot]
     NTFS, blocksize=512, 3161 KB / 3087 KiB
   P MS Data                354099734  354120472      20739 [NO NAME]
     FAT12, blocksize=4096, 10 MB / 10 MiB
     MS Data                358938549  358944722       6174
     NTFS found using backup sector, blocksize=512, 3161 KB / 3087 KiB
     MS Data                358944722  358950895       6174 [Boot]
     NTFS, blocksize=512, 3161 KB / 3087 KiB
   P MS Data                358951010  358971748      20739 [NO NAME]
     FAT12, blocksize=4096, 10 MB / 10 MiB
     MS Data                363749573  363755746       6174
     NTFS found using backup sector, blocksize=512, 3161 KB / 3087 KiB
     MS Data                363755746  363761919       6174 [Boot]
     NTFS, blocksize=512, 3161 KB / 3087 KiB
   P MS Data                363762034  363782772      20739 [NO NAME]
     FAT12, blocksize=4096, 10 MB / 10 MiB
   P MS Data                371716138  371719017       2880 [EFISECTOR]
     FAT12, blocksize=512, 1474 KB / 1440 KiB
     MS Data                371720053  371726226       6174
     NTFS found using backup sector, blocksize=512, 3161 KB / 3087 KiB
     MS Data                371726226  371732399       6174 [Boot]
     NTFS, blocksize=512, 3161 KB / 3087 KiB
   P MS Data                377878122  377881001       2880 [EFISECTOR]
     FAT12, blocksize=512, 1474 KB / 1440 KiB
   P MS Data                377881002  377883881       2880 [EFISECTOR]
     FAT12, blocksize=512, 1474 KB / 1440 KiB
   P MS Data                421662274  421665153       2880 [EFISECTOR]
     FAT12, blocksize=512, 1474 KB / 1440 KiB
     MS Data                421674913