It is neither more nor less rude, nosy or intrusive than asking any other personal question. If starting a friendly conversation with a “victim” is appropriate, then there is nothing wrong with using this as an introductory question. In a situation where it is not appropriate, such as interrupting two people who are already engged in a conversation, then no question is OK.
I’ve done this, and never found anyone bothered by it.
I was at Disneyland once, and there was a family ahead of me with pronounced accents. We’re in a long line, with lots of time. So I asked.
“I couldn’t help noticing your accent. Where are you from?”
“Go on and guess.”
“Adeleide?”
“Melbourne, but I’ll give you the yellow ring.”
We chatted away like old friends for the next half hour in line!
It’s not English I struggle with, it’s Scottish. 
Accent, anyway, fortunately the words are in English even if I can’t always decipher them.
People here have started to guess Irish for me, as there are some similarities between it and an American accent with slight hints of Scottish pronunciation. I think I’m developing a Transatlantic accent, or a case of Irritable Vowel Syndrome.
Better than inconsonants, I guess.
Ba dum bum.
New Zealand, geographically, is as far from Australia as London is from Moscow.
There are probably almost as many Kiwis in Melbourne as Russians in London, but that doesn’t make a Russian British, just as it doesn’t make a New Zealander Australian.
I think asking ‘Where are you from?’ is quite personal enough, if talking to a complete stranger. Answering ‘I don’t know, I’m adopted’ is good if you want your inquisitor to feel awkward. 
I gather that in World War II, with huge numbers of American military in the UK; this or something related to it, at times caused a bit of awkwardness between “residents” and “guests”. With British – and especially English – folk tending to be reserved, and to attach much importance to privacy: the Americans’ very frequent practice of, pretty well on meeting, asking / telling each other where in the States they came from, often struck the Brits as odd. They felt it to be a bit off-puttingly inquisitive; and there was a trend of thought along the lines of, “why are these people so hung-up on this particular stuff?” In those years, many Brits concluded that Americans were rather weirdly obsessed with geography.
Yes, that’s right… It is a personal question.
But you are wrong in thinking asking strangers personal questions is okay. It is rude.
Asking where someone is from is okay, as long as you accept their first answer and do not proceed to rephrase or ask “but where are you REALLY from?” or “where were your parents from?,” etc. because your nosiness compels you to get to the bottom of why they have a “strange” name/appearance/accent.
Many people have worked hard to speak the local tongue without a foreign accent and pride themselves in having accomplished same. They think they are fitting in. You pointing out their failure is obnoxious and often quite unwelcome.
When you learn a foreign language and a native speaker says you do not have an accent, it is a compliment. How is it not obvious that the opposite may not be taken well?
The thing is, I am American. I may have a foreign name and foreign features but I can’t help that. At least I am actually “from” somewhere else, in that I was born in India. My SO gets the same crap because he is ethnically Chinese but he was born in long island and is named after one of our country’s founding fathers, for heaven’s sake. He is completely american and yet still bears the “foreign” classification.
Upon learning that someone’s origins may be “foreign,” I have even witnessed people post-facto imagining accents that do not exist. “Ah, I thought so… You have a slight accent” they will say, trying to impress people with their discerning ear.
My ex, who was born in another country but relocated as a small child, was once absolutely livid to be told he had “almost no accent.” I still tease him about it, but really we are making fun of the twit that said it.
My wife is Egyptian and likes to ask people where they’re from if she suspects they are Arab. Often this question results in a pronounced reluctance to answer due to some of the political baggage of our times. This is especially true when the person is Palestinian. I have told her that if she really wants to know, she needs to volunteer where she is from first. She has lighter-than-average skin tone for an Arab and is sometimes mistaken even in Egypt as European. So it’s not obvious that she is asking out of a sense of fellowship.
It’s not outright rude but it might make some people uncomfortable.
Once, many years ago, I had the joy of attending an actual diplomatic reception at a U.S. embassy in another country. (Bahamas.) I was chatting happily with the U.S. Charge d’Affairs, and, quite naturally, we asked each other where we were from. I said California, and he said New York.
He said that this always happens with Americans who meet abroad. And the answer (he said) is nearly always the state. Sometimes, it’s the city, like Chicago or Los Angeles. But most often, the state. He said it’s like we’re from fifty different little countries.
(Geography is so incredibly vital to the founding and growth of the U.S., how could we not be obsessed with it?)
Makes excellent sense when you put it this way. I’d hazard a guess that seventy-odd years ago, people perhaps tended to be less aware of the ways of other countries, than nowadays? Also, the situation in Britain in the later stages of WWII was such that – vitally necessary though the American presence was, and good though relations, on the whole, were – the British populace would have had to be superhuman, not to feel the occasional twinge of resentment vis-a-vis the very numerous transatlantic visitors. Hence perhaps an element of looking for traits to find irritating…