How should I politely ask for someone's time to interrupt them, like in English:
Do you have a minute?
May I bother you for a moment even though you're quite busy?
When I want to interrupt someone in front of me I would say:
Verzeihung, haben Sie bitte mal einen Moment Zeit?
Entschuldigung, darf ich Sie mal stören?
The leading word (not important which one you choose) gets attention to the question itself. To make the question polite, it's important to give it a polite pronunciation. I would not tell the guy that he's busy, he knows it himself.
From my own experience as a busy person I do not recommend lengthy apologies as these even if they may be polite tend to raise my pulse by at least 10 beats.
Depending on how busy the person is you are interrupting you should keep the interruption as short as possible. Therefore it is perfectly alright and accepted as polite enough if you just say:
"[Entschuldigung,] haben Sie kurz Zeit [für mich]?" *
*words in brackets add politeness only if really needed
In a less formal setting (usually when you address people with "Du" but also possible with people you don't know) you may just ask
Unabhängig, wie du jemanden unterbrichst, bedenke, dass du es schon in dem Moment getan hast, wenn du sowas wie Do you have a minute? sagst/fragst. Nicht selten bekommst du eine Antwort in der Form: "Eigentlich nicht, aber jetzt hast du mich ja schon unterbrochen."
(Independent of the way you interrupt someone, pay attention on the fact that you already did, even just asking Do you have a minute?. It's not infrequently to get an answer alike: "No I didn't but you already bother me.")
In Ergänzung zu den bereits erwähnten Möglichkeiten (In addition to the mentioned possibilities):
vorangehende Frage / precedent question:
ohne vorangehende Frage / without precedent question:
You're fine with simply saying
(The latter is formed by simply omitting the first syllable and is slightly colloquial.)
This would not be considered rude (by anybody I know). Although you could certainly manage to intonate it such that it sounds a bit demanding, but you can do this with basically everything. As long as you put it clearly as a question it should be okay.
Use these Phrases - I am Sampath - English Teacher May I speak with you for a moment? Can I have a word with you? Can I talk to you for a minute? Can I talk to you? May I have a moment with you? Do you have a minute?
May I have a moment? Can I have a minute? May I be excused? Excuse me for a moment.
On sales calls, I use in English, "May I stop you from working for two minutes?", which I will translate quite badly into German as "Mög ich Ihnen abstellen vun arbeiten auf zwei minuten?" There are the occasional jackasses who will answer rudely, but it shouldn't bother you. I just turn and walk away.