I can't answer your third question, but I can answer the first two. The beginning of the idea of a "state" as we know it today began in 1648 with the Treaty of Westphalia ending the wars of religion in Europe. This treaty basically made clear that every king/ruler has his land, his subjects, his religion, and it's his right to do as he pleases in his land. A big part of this treaty was the idea of "non-interference" between states.

A "state" is defined as an entity with territory, a government, subjects, and most importantly, recognition from other states. That's pretty much it.

A nation though, is a cultural concept. A "nation" is defined by a group of people with a common culture, history, language, and experiences. There are several more things that go into it, but that's the gist of it.

To use the Middle East as an example, the only thing keeping ISIL from being a state is recognition from the rest of the world. They recognize that they exist, but deny their legitimacy. They also wouldn't be a nation. The Kurds though, would be considered a nation. They have a shared identity, history, and a rough geographical "home". They do not though, have their own state. Their territory is split between several states in the region. The Kurds desperately want to break off and form their own state, which they call Kurdistan. If they did this, and they were internationally recognized, then Kurdistan, a state run and populated by the Kurdish people would be the definition of a "Nation State".

Nation states incoporate an imagined community where there is a sense of shared identity among the populace. Imagined because those who percieve themselves as part of that community will never interact with everyone in that community and by most measures the community is an abstraction.

Today nationalism is such a strong ideology that there is no real alternative. Through education, culture, media, states foster a sense of national identity. Historically composite monarchies particularly were more diverse incorporating numerous legal, lingustiic and cultural traditions, only unified by a common Monarch. A collective identity wasn't seen as necassary to a functioning state.

The first nation state is a difficult debate because it depends on the explanation for the growth of nationalism that you believe. Either the primordialists: nationalism is inherent and old. Or the modernist: nationalism is created and modern.

The idea of the nation state is particularly relevant in German and Italian history. Both states as we know them today were once fragmented into smaller states, while being part of a similar language group and other cultural similarities they were not unified. Nationalists then in the 18th/19th century fostered a greater sense of common identity and aimed for the incorporation of this Italian/German identity into one state. Italian/German identity would have been seen as a nation but without a state until they established those states in the 19th century.

Anderson, Benedict R. O'G. (1991). Imagined communities: reflections on the origin and spread of nationalism London: Verso.

"A nation is a soul, a spiritual principle... The nation, even as the individual, is the end product of a long period of work, sacrifice and devotion. The worship of ancestors is understandably justifiable, since our ancestors have made us what we are. A heroic past, of great men, of glory that is the social on whicht the national idea rests. To have common glories in the past, a common will in the present; and to have accomplished great thing together, to wish to do so again, that is the essential condition for being a nation. One loves in proportion to the sacrifices which one has approved and for which one has suffered... Common suffering is great than happiness. In fact, national sorrows are more significant than triumphs because they impose obligations and demand a common effort."

To summarize Ernst Renan's thoughts from What is a Nation State? (p.26-29), the nation (as an abstraction) is simply an idea that is in constant struggle to be made more real. To be made more concrete by what the citizens are willing to sacrifice for it (most commonly their toil, efforts, and lives).

The writings of hyper-nationalists seem to lend credence to Renan's thoughts on the matter, Hitler, on the 2 million dead German soldiers of WWI, remarked: "The most precious blood had sacrificed itself joyfully, in the faith hat it was preserving the independence and freedom of the fatherland." (Mein Kampf p.201) and he mentioned earlier that "The state-forming or even state preserving forces are...the ability and will of the individual to sacrifice himself for the totality." (p.151) If you are interested in the topic, definitely take a look at N.H. Bynes' The Speeches of Adolf Hitler because his language and wording is absolutely littered with the concepts of soldier sacrifice, deification of the nation, etc. Christopher Reuter's work on the Japanese Kamikaze (My Life is a Weapon Chapter 6) is also particularly interesting when considered in Renan's framework.

Anyway, as you can see it is a complicated question with a ton of different interpretations and answers. The question you ask is one that is still living and breathing and really has no definitive answer. This is just some of the stuff that I happen to subscribe to and I hope it helps to answer your question.