You can try formatting your drive as UDF(Universal Disk Format). It is the format for use on CD's and DVD's. Most modern OSes will be able to read and write to it.
Right now, looking at my data on UDF formatted drive, Linux file permissions seem to be preserved. So far, it's worked for me.
Another good thing about UDF formatted drive is that it can store a single large file of up to 16 Exabyte(correct me if I'm wrong.), whereas Fat32 can only store a file of size 4GB or less and MAX partition size for FAT32 is only 2TB.
It works good on Win7 and 8. For older Windows OSes like XP and 2000, you can read from the drive but you have to install some sort of driver to write to it.
For Mac, OS X 10.5 and above has full compatibility.
Here's a full compatibility chart.
UDF Compatibility Chart
On Ubuntu, follow these steps to format a drive as UDF.
sudo apt-get update
sudo apt-get install udftools
Okay, now you want to delete the current partitions in the target drive.
You can either use a GUI tool like Disk Utility, or do the following.
sudo blkid
Find your drive in the output. (they look something like /dev/sdb or /dev/sdc)
Now do the following, but replace the 'x' in /dev/sdx to point to the drive that you want to clear its partition. Do this for both lines of code.
sudo dd if=/dev/zero of=/dev/sdx bs=1M count=1
sudo mkudffs -b 512 --media-type=hd --utf8 --lvid=DriveLabel --vid=DriveLabel --fsid=DriveLabel /dev/sdx
You could alter where it says 'DriveLabel' to your liking.
That should be it.
Actually, I do this slightly differently, but decided that this method was easier to follow. I referenced this method from this site.
I hope this helps someone out there.