Is it possible to use a workflow to update a field that is on a different record than the one that the workflow is running on? If so, how can you accomplish it?

You will have to use a custom action script for that.