1) Excuse me, could you tell me ...
Speaking to someone you don't know on the street, for instance. There is no need to use any form of address if you start off with "Excuse me.."
2) Excuse me, miss, ...
This might be used, for instance, in a restaurant or shop when speaking for the first time to the waitress/assistant, regardless of age.
3) Hey, mister ...
Not really BE, and only possible when children speak to strange (=unknown) men, and even then, not recommended.
4) Lady.
Can't comment on this US usage. I don't think you would hear that in UK.
5) Ladies and Gentlemen ..
When addressing a group, for instance in a meeting.

Generally, with small talk, it's a good idea to ask someone's name early on and then use it. "I'm sorry, I didn't catch your name. / I'm sorry - you did tell me your name and I've forgotten it. If you use "sir" or "madam" it sounds subservient - i.e. you would only use this form to a boss/employer/customer.

Meine Kommentare in Java-Kommentarklammern, also '/*' und '*/':

1.) Ich denke, soweit sicher ist, dass man z. B. 'Excuse me, sir/madam, could you..' ohne Nachnamen sagt. Frage:
- ist das speziell British? /* Nein */
- sagen wir, man mach smalltalk mit Vorgesetzten (nicht on first name terms): Wäre es da auch denkbar, dass man ab und an im längeren Dialog da mal ein solches 'sir', 'madam' fallen lässt ('Absolutely, sir' etc.), um nicht immer 'Ms X' oder 'Mr Y' zu sagen. /* Durchaus */

2.) In einem amerikanischen Roman sah ich, dass auch sinngemäß "Excuse me, miss, could you" gesagt wurde
- ist das speziell amerikanisch? /* Heute eher: 'Ms'. Steht für 'Mrs' und 'Miss' */
- wann sagen die Amerikaner "ma'am" (ist ja wohl auch madam) und wann 'miss'? Ist es eine Altersfrage? /* Ma'am ist das Gegenstück zu 'Sir', also sehr höflich. 'Miss' hört man nur noch selten. */
- ist miss eher informell (z. B. daher untypisch für höflichen smalltalk?) /* Die einzige Gelegenheit, wo Du heute noch regelmäßig 'Miss' hörst, ist wenn eine betagte Person eine junge Kellnerin ruft. */

3.) Manchmal hört man auch "Hey, Mister, could you..."
- Brit Engl or Am Engl? /* IMO eher amerikanisch */
- informell/überhaupt "richtig" (im Sinne von akzeptabel/nicht offending)? /* Wohl eher etwas unhöflich. Ich würde es nur dann sagen, wenn mich einer blöd anmacht. Also z.B.: Hey, Mister, could you piss off now? */

4.) In einem smalltalk dialogue (recorded) sagt ein Amerikaner "No, lady, ...."
- finde ich seltsam. Ist das ggf. etwas salopp? /* Ja. Aber es ist durchaus nicht ungewöhnlich. Auch nicht unhöflich. Aber eben salopp. */
- in Br.Engl. ist Lady doch ein Adelstitel, also nicht wie oben verwendbar, oder? /* Habe es von einem Briten noch nicht gehört. Aber das muss nichts heißen. */

5.) Wie begrüßt man bei direktem Kontakt (NICHT im Brief, sondern sagen wir auch smalltalk situation, oder eine Ansprache vor einer kleinen Gruppe oder so) Frauen und Männer gleichzeitig?
- British/Ameri. En.: Dear Madams and Sirs?? Ladies and Gentlemen (ist das nur Am.Engl). (klar kann man 'dear audience' sagen oder sonstwie drumrum, aber wie geht es mit 'Damen und Herren'?) /* Es heißt standardmäßig 'Ladies and Gentlemen'. */