Hello,
a few ideas:
First, I agree with Ken: The best way would be a restore from backup, if available.
And the next best seems to be the tar method.
But ...
tar is /usr/bin/tar, and so it may be not available, or it may not have exec permissions either...
Can you try rcp or scp? -p flag should preserve permissions.
An if all this fails: There is a trick that will allow you to ftp your chmod file with exec permissions:
For this you will need, on your target machine, some file that already has exec permissions, and that you don't need any more, and so you may overwrite it. Lets say its name is /path/oldprogram.
ftp /usr/bin/chmod to /path/oldprogram, then /path/oldprogram will still have exec permissions, and the contents will be chmod.
Then you may do a /path/oldprogram 777 my_files .
hope this helps