Tenpenny - Tenpenny might already be gone if you did the Tenpenny Tower quest before this one. That's alright. You can just try to lie to Crowley and claim a 25 cap reward for ensuring his death. Even if he sees through it, it won't change the quest much. If he's alive, then go up to the top of Tenpenny Tower and get past his guard. Talk to Tenpenny on his balcony and ask him about Crowley. If you pass the speech checks, you can find out that Crowley was sent to Fort Constantine as part of a raiding group. He should also be able to tell you where it is.

click to enlarge
Don't just kill him once you've gotten your information though. Tell him that Crowley wants him dead. He'll give you a counter offer to kill Crowley. You can just listen to him and go kill Crowley. The ghouls in Underworld don't usually seem to care. Regardless, if you pass the speech check to get 300 caps, he'll give you 100 upfront. If you want to follow Crowley, take the caps and blow his head off in VATS.
Ted Strayer - Ted is a drug user in Rivet City. Just track him down in the common area. If you have Strength higher than 6, you can just scare him into giving it to you. You can also buy it off him or just pass a speech check. He doesn't know anything about it, so this one is easy.
Dukov
- Dukov is in Dukov's Place out on the edge of the city. Just go inside his party house and talk to him. With a few speech checks you can find out about the mission and get a marker for Fort Constantine. You can also convince him to give up the key for free. You can also buy it for 200 caps. This is a little wastefull though. You can use the Lady Killer perk to get one of his girls to get it for you. If all else falls, you can talk to Cherry. She'll offer to pickpocket it if you take her to Rivet City. Just fast travel there once she has it.
Dave - Dave's out at Dave's Republic in the northeast corner of the map. Just walk up to the gates and ask to be let inside. This one is probably the trickiest for a speech check. You need to pass a tough speech check and convince him that you're an ambassador. With another 2 checks, he'll hand it over as a gift. Just keep saving and reloading. You can also kill him or pickpocket him if you run out of patience.