I deleted a folder in Ubuntu, how can I recover it?

The folder is massive (390GB) and contains many different files. The file system is ext4

I was about to copy this file to another hard drive using gksudo nautilus so I didnt have do a massive chmod operation on the destination hard drive, but then I accidentally hit move to trash, which in gksudo nautilus means permanent deletion. I checked the trash but it's not even an operation...

I have seen tools like testdisk and other recovery tools but none that can recover and whole folder because its made up of different files.

I don't think that this would work but if I deleted the partition could I just recover the whole partition at once?

Or would this be wrong because i have already deleted the partition's content? This is my first job in Linux IT.

I don't have a backup... I was trying to make one because the old backup drive died :(

Not speaking from personal experience, but I've heard good things about extundelete. You know to unmount the partition with the deleted files immediately, right? And never mount it again, (read-only is ok), until you have finished attempting to recover files?

For best results you'll have to download and build extundelete from source. That partition is still unmounted, right? Easiest though, and again I haven't actually tried this, boot from a live USB/DVD, don't mount the affected partition, sudo apt-get install extundelete (a slightly out of date package is in the Ubuntu Universe repository), cd to a directory on some other mounted partition with sufficient free space to hold your recovered files, and just run the program. You'll want to check the command reference, but the first thing to try should be something like

$ extundelete /dev/sdX --restore-directory /home/user/that/directory/you/deleted.