If someone asks me if I’m from Iceland, is it correct to answer “no, I’m not from Iceland”?
Sure. Unless you really are from Iceland.
In which case it would still be correct, but it would be wrong. 
It sounds like I’m answering the question twice. “No” answers it and “I’m not from Iceland” answers it, but saying “No, I’m not from Iceland” is like answering it “No and I’m not from Iceland”, which sounds incorrect.
IMHO, it’s a little redundant, but not incorrect.
It only sounds that way if you’ve somehow forgotten the way people actually speak…
Which is to say, sure, if you like, you can consider it to be answering the question twice, in some sense. But so what? “Are you hungry?” “Yes, I am.” “Oh my! You’ve answered my question twice. I… I don’t know how to go on.”
Inquisitor: “Are you from Iceland?”
You: “No.”
IMO it is not necessary for you to repeat the question in the answer. That is why it sounds incorrect and redundant.
It’s also not necessary for you to use the word “No” in the answer. Many things aren’t necessary. That doesn’t mean they’re incorrect. Language does not operate on a “Whatsoever isn’t necessary is prohibited” basis.
In particular, it’s neither necessary nor prohibited for you to combine or avoid combining the word “No” with a declarative restatement of the question. Do whatever you like; it’s fine.
The English language could not possibly function without repetition, redundancy, and emphasis. At least that’s what any study of the history of the language tells us.
A proper study of English also tells us that the oral language and the written language are, in essence, separate dialects of one another and that rules and styles for one should never be applied to the other. The same goes for formal language, casual language, regional languages, and slang, either written or oral.
There are lots of people who don’t understand this, and regurgitate whatever was said by their favorite English teacher, but you can safely and totally ignore them. As I’ve said in earlier threads about English, they are always wrong when they post those memories here, without any exceptions I can remember.
Context and setting always decide what is “proper” and what is not, and the boundaries of “proper” have stretched so far in recent years that the language may as well be made from Spandex.
It’s correct… and so is “No, I’m not”… so is shaking your head from side to side saying “No, I’m not”…
When someone politely asks you a question, you should answer with more than with just a “No” or “Yes”. “No, I’m not from Iceland” addresses the specific question, and it shows the person you have heard the question.
And this is not just restricted to English - using Polish as an example, answering just “Nie” is a little impolite - saying “Nie, nie jestem” is more polite.
It’s just as proper as “Yes, we have no bananas.”
Simply saying “no” can seem abrupt. The person who asked the question may wonder whether offense has been taken. That’s one reason for the form, “No, I’m not. . .” It’s a softer way of saying the same thing.
Simply saying “no” is abrupt, whereas responding to “are you from Iceland?” with “I’m not from Iceland” just sounds plain weird. It’s a complete sentence grammatically, but usage requires it to be accompanied either of a “no” in front or of a statement indicating where you’re from in back - or both.
“No, I’m not from Iceland, I’m from Norway” is perfectly kosher - and you’ve just answered thrice!
That’s not really correct. The convention is that “yes” is used in positive answers, and is strong enough to twist around a negative question. “Yeah” doesn’t always have this power.
“You don’t have any bananas?”
- “Yeah, we ran out this morning. Sorry.”
- “No, we don’t have any.”
- “Yes, but we haven’t gotten the chance to put them on the shelves yet.”
The phrase “Yes, we have no bananas” deviates from this convention, which is why it sounds odd to a native English speaker.
Perhaps the redundancy of responses such as “No, I’m not from Iceland.” is to avoid confusion from one-word answers.
It’s a perfectly acceptable, grammatically correct answer. Particularly if the original question was “So you aren’t from Iceland?” in which case a simple “No” would be rather ambiguous.
I’m not from Iceland, I’m from Sainsbury’s
Ever take a language class? 
Just to clarify, in case my last sounded snarky: In language classes the student is expected to include the redundancy to show that he knows how to form the response, instead of just giving a ‘yes’ or ‘no’. For example, ‘Do you have a pencil?’ ‘No, I don’t have a pencil.’:
*Hast du einen Bleistift?
Nein, ich habe keinen Bleistift.*
A simple ‘Nein.’ or ‘Ich weiss nicht.’ (‘I don’t know.’) isn’t acceptable.
Does Latin count (four years in HS?) I am teaching myself to speak Spanish; so I do not think that counts either.
I did not think you were being snarky:)
I personally am incapable of answering a yes/no question. I always must explain my answer. Many people complain to me of this.