The thing is always remember is that politeness is speaker and listener relative. To someone younger than you, even if they are a complete stranger, you could get away with a lot.
Here's the way I ask my friends:
今何時? (rising on the ji)
Since we're friends it's not rude. Also, had I met you long enough to get your name I might feel that form was appropriate. After all asking the time isn't a huge favor. I'd probably have to reconsider my approach if I wanted to borrow some money.
Here's the most polite way I can think of outside of circumstances where you might need keigo. (Once again giving the time isn't a huge favor so going more polite might seem pretty extreme to people.)
すみません。あの、今何時でしょうか。
Pretty much all of the extra wording in there are softeners. It goes something like:
すみません - Excuse me!
あの - Well, (I don't want to bother you but ...)
今何時 - What is the time now?
でしょうか - softer form of desu ka. this makes it sound more like, "what time do you have?" rather than, "what is the exact atomic time at this very instant?"
Also, if you are anywhere but Tokyo that probably sounds really girly too. (No one in Tokyo seems to worry too much about sounding girly except the old men.)
If I were you I would stick with 何時ですか。 for now. If your Japanese sounds too natural you'll probably get blasted with an answer you can't understand.
One more thing about this phrase that I'm surprised no one mentioned! It is not limited to just finding out the time. If you see people that look interesting to talk to just ask them the time. Often the conversation won't just stop after you've gotten your answer.