One of our 'admins' accidently did a chmod 750 (as root) on /bin instead of the folder he was supposed to chmod. Now the whole server is trashed as the file system is corrupt. Does anyone know a good way to change that back, or are we looking at a full rebuild here?
What jhill10110 said is probably your best bet. When you boot off of the live cd, you will likely have the option of entering in a 'rescue' mode and then having the rescue application mount everything under a typically existing directory.
Say it mounts everything under /var (just making one up). To access your 'ls' command. Instead of /bin/ls, it would be found at /var/bin/ls. So you could cd to /var/ then run your commands. Once you've changed mode for each directory (recursively, if necessary) then you can reboot, taking the boot media out as you're able.