What are some methods (other than task based usability testing) to identify the impact of an interface redesign on users? Specifically, if an interface used by the same user base is redesigned, how can you measure how much more or less time it will take for them to use it.
You should have a good baseline usability study of your existing product, which measures time-on-task, perceived performance, and satisfaction. That gives you a solid understanding of where you stand today with your product.
You can't accurately measure time-on-task without real running code. However, you can measure other things that will indicate time-on-task improvements (and might actually be more important than simple time-on-task). For example, you can study early wireframes, mockups, or prototypes to understand whether users think that the new UX will improve their ability to complete a workflow successfully, complete a workflow more quickly, complete it with less cognitive load, or complete it with a higher level of satisfaction.
Another comparison that you could draw would be number of clicks. How many clicks does it take to complete the workflows in the existing product, and how many clicks does it take to complete the workflows in the new product? This doesn't necessarily translate to a faster time-on-task, increased ability to complete the workflow, or increased satisfaction. However, it has the benefit of being an easy early heuristic evaluation that can be done on both the existing product and early designs of the new version, and fewer clicks is often one component of an improved design.