Executive Summary
If you work overseas or in international business, you will come across a large amount of non-native English speakers. Ideally you will be able to understand them all, but if not, you need to overcome the accent and find a way to communicate effectively.
Non-Native English
There are upwards of 400 million Native English speakers in the world. By some estimates, there are upwards of 1.5 billion English speakers. Even with native speakers, I have met many Americans who have issues understanding Australians, or the Scottish, or Welsh (even when they are speaking English). The point is that it's a world full of varieties of English, and you're going to have to get used to them.
Understanding Better Through Context
Understanding is not 100% about accent. There are native English speakers who couldn't string a sentence together to save their lives. Context is also important -- even the heaviest of Indian accents is a lot easier if you're discussing cricket than if they are explaining the content of a random newspaper article you haven't read and don't know the subject of.
I find it incredibly useful when dealing with non-native speakers to set the context myself, or if they are leading to confirm the assumed context beforehand. For instance:
Sorry, I didn't fully understand your question. We were discussing topic, right? Would you mind repeating the question a bit more slowly for me?
The two bolded words are leading questions allowing me to confirm the context. If it was not a question, then they will correct it (and you will know you don't need to respond). And you are confirming the topic, which will allow you to focus your brain on the important portions related to that topic.
Coping with Language Barriers
Sometimes you just can't understand the other person. I cannot understand Welsh English, and they are (allegedly) native English speakers. Repeat as they may, it just isn't working, and there is no communication going on. When you are negotiating a business deal (or having an interview), you cannot just change the person you are speaking to without saying, "Sorry, having the appropriate person do this is less important than me understanding easily." You are putting your comfort above the other side's needs which is definitely not a great sign.
The secret to dealing with language barriers is to be honest. There is very little rude with a non-accusatory, "Sorry, I am having some trouble understanding your accent, is there any chance you could slow down a bit?" If the conversation is important, then they have an incentive to slow down. And chances are if their accent is that thick, they have come across this issue before. If that still doesn't work, fumbling along and blaming static is not an effective tactic, because when you're face to face, you will lose your excuse, and haven't shown you can overcome a language barrier.
I have been in meetings where there was a translator (just in case), or where documents were sent out ahead of time in English so that even if someone missed something, they would have better context written down to refer to. I have seen telephone conversations shifted to a videoconference so you can see the movement of lips and body language to get added cues to assist communication. And I have even seen voice done with an open chat session so that things can be typed if there is confusion.
Suggesting any one of these (though in the case of an interview, asking for a translator probably isn't ideal) should be seen as practical problem solving, not rude.