I just saw this, sorry I realize it is an older post. Well, this is what I do. One day a week, I do intervals on a stationary bike which kills! It is so much harder than I thought and actually a lot like running. I do this instead of a run once a week. Then, once a week (if the weather is lousy) I do intervals on a treadmill instead of a run outside. Two days per week, after the cardio or a run, I do strength training using dumbells, exercise balls, etc. I have noticed that running has gotten a lot easier since I started the strength training. I do relatively low weights, but high reps (25-30 reps). Believe me, it is HARD! Well good luck!