I've been asked to add a step to a workflow I've written but there are already many documents currently inside this workflow that I would like to switch over to the new workflow.
Can this be done easily? I've looked on google and places like this: http://stackoverflow.com/questions/357032/how-to-upgrade-a-long-running-sharepoint-workflow-already-in-production, but I can't find anyone actually doing what I'm trying to do.
I'm assuming that's because it can't be done?
To my experience you should create the new version of the workflow and run your documents trough this new workflow again. I actually tried what you are asking for I could not find any information nor do it.
The workflow instance is serialized to database (via .NET serialization) when it is idle, and deserialized into a workflow object when awaken. If you modify the class of the workflow instance, the runtime will choke when trying to deserialize the idled workflows with the 'old' structure.
If you're careful, you can add some degree of change to a running workflow: for example, you can change code in code activities, or change some logic as long as it does not affect the 'physical' structure of the process (we have managed to do this several times, fixing a bug in the code and overwriting the dll's in place without reinstalling the workflow feature). What is a big no-no is adding/removing fields from the class that holds the workflow or changing their types.
If you need to do some major changes (adding/removing activities, etc), you're better off deploying the new workflow as a different workflow. We usually deploy different versions of workflows using a naming scheme like foowf-0.1, foowf-0.2, etc.