You're really asking about the requirements for Statehood - whether individual States will recognise another, as has correctly been noted, is largely a matter of politics and policy, which is distinct enough of an issue that we need not concern ourselves with it here.
You're asking too many questions for me to answer here, particularly the last one, so I'm going to consider just your basic question: how does one create a new State?
There are a few theories that describe past processes of gaining Statehood but the current and generally authoritative one is the Montevideo Convention, which codifies customary international law.
The state as a person of international law should possess the following qualifications: (a) a permanent population; (b) a defined territory; (c) government; and (d) capacity to enter into relations with the other states.
The Convention also states that Statehood is independent of recognition by other States - this means that whether you are recognised by the United States, France or Japan is largely irrelevant to whether or not you are a State.
A permanent population
This isn't too difficult - just find yourself some territory and occupy it, permanently. This doesn't mean your populace can't travel, only that the territory needs to be their permanent residence.
A defined territory
This is probably most pertinent to your desire to create a new State into the [sic] international sea waters - you can't create a State on a boat, or even on a network of boats.
Fairly easy, the threshold for government is that it need only be sufficient and effective - it doesn't need to be democratic, or fair, etc.
You could set the government up openly as a dictatorship and still fulfil this requirement as long as it was effective.
Capacity to enter into relations with other states
This is where many purported States fail - generally, micronations and quasi-States are not recognised by other States, and so their capacity to enter into relations is difficult or impossible to gauge.
So, to summarise:
- Establish a permanent population
- Demarcate a defined territory
- Establish a government
- Get other States to enter into relations with you
If you do all these things, you have technically fulfilled the requirements for Statehood under the Montevideo Convention.