I have 3 dogs, all rescues, too.
My two adult dogs (both German Shepherds) run with me. My male does long trail runs and some longer city runs (as well as all short distances) with me, but he can be a bit spooky sometimes in the city (he was brought into a country shelter as a puppy and spent 3 years there, and while I've taught him traffic is OK, we have to plan all on-road routes running on the sidewalk facing traffic, after a car jumped the curb at us last winter he's got a real thing about which sidewalk he's on).
My female I've built up her distances, she has hip dysplasia and I actually stopped running with her after her diagnosis (6 weeks after I adopted her) but decided to go slow and start her running again (she also lost a lot of weight after I adopted her and the HD is being treated). She does shorter runs, she's now at the point she can go over 10k on a run. I had planned on not adding to her distances we'd gotten to that point but she loves running so much I'm going to see how far she can go. She's usually pretty slow and I let her pick the pace, except if she sees another dog - she is very aggressive to dogs outside of our pack (always on lead and muzzled outside; I have a special running muzzle for her as well as police muzzle for walks and other stuff) - she gets so excited (in a bad way) by the other dogs I've seen her increase her pace by 50 seconds/kilometer (the dog had gone down a side street, I wasn't letting her run it down, but she was just so excited anyways).
I run my two adults together with a coupler.
My puppy (husky/terrier) is about 11 months old. My understanding is you need to wait for the joints to finish growing/forming before doing high-impact exercise like running w/them, especially on pavement, so I'll be waiting until around 18 months and then starting running. He is a good hiker though and I'm sure he'll be an excellent runner!
Here's my male GSD out on a trail:
http://www.facebook.com/...a3a&id=630190844