I'm pretty familiar with computers (been programming for quite a bit and have a little *nix experience). However, I'm by no means a linux expert, especially when it comes to a situation like this.

I have an external hard drive that I'm currently using for data. It's plenty big (1tb) and is only about 20% full. I would like to throw a linux setup on there (ubuntu, pclinuxos, etc) and boot from the external. Now, if I were able to format the drive, partitioning would be simple and not an issue. However, I cannot format as I have no external media large enough to hold all the data. Thus, I was wondering if it'd be possible to add the required partitions without destroying the data.

Well, you can first defragment your existing partition (if it's FAT or NTFS) and then shrink it with a partition manager of your choice (Gparted - I guess it even comes with the PARTED Magic LiveCD). I've shrunk a partition before with that LiveCD and the shrink cut me the boot section of Linux. If this happens, use a LiveCD to reinstall GRUB.