I work with a code base that is over 500K lines of code. It is in serious need of refactoring. There have been refactoring efforts identified that will take longer than the normal two week sprint. These can't be broken up into smaller tasks as I have seen suggested in other answers on this site. The product needs to work at the end of the iteration, and partial refactoring will leave the system in an unusable state as the dependency between items is horrible. So what would be the best way to approach this hurdle? Again I mention, breaking it down into smaller pieces is is not an option, that has already been done.
Update: People seem to need an explanation of why this can't be fit into a 2 week sprint. There is more involved in a sprint than just writing code. We have a policy of no code without tests. That policy did not always exist and a large portion of the codebase does not have them. Also some of our integration tests are still manual tests. The issue is not that the refactoring itself is so large. It is with the fact that small changes have an effect on many parts of the system, and we need to ensure that those parts still operate correctly.
We can't put off or extend a sprint because we have monthly hotfixes. So this change extending past a sprint cannot stop the other work being added to the hotfix.
Refactoring vs Redesign: Just because our development process is not efficent enough to handle this refactoring in a two week cycle does not warrant renaming it to a redesign. I would like to believe that in the future we could accomplish the exact same task within a two week cycle as our process improves. The code in question here has not had to change in a very long time, and is quite stable. Now, as the direction of the company is becoming more adaptable to change, we want this portion of the code base to be as adaptable as the rest. Which requires refactoring it. Based on the answers here, it is becoming apparent that there is missing scaffolding necessary to make this refactoring work in the time frame of normal sprints.
I am going to do the branch and merge approach that Corbin March suggested the first time so we can learn more about these problem areas and how to identify the missing tests. I think moving forward, we should take the approach that Buhb suggested of identifying the areas that are missing tests and implement those first, then do the refactoring. It will allow us to keep to our normal two week sprint cycle, just like many here have been saying should always be the case for refactoring.