What happens when for example an unknown vulcano erupts in a part of an ocean which does not belong to any country? Which countries qualifies for claiming this piece of newly formed land? Has a situation like this ever occurred in the history?
Newly formed land would in effect be no different than newly discovered land. This means, that islands which are formed within the 200 mile limit the U.S. recognizes, for example, would belong to that country. Lands outside of that 200 mile limit would be subject to laws of any "terra incongnito" and be subject to annexation.
This story in Nat Geo, for example, talks about the acquisition of minor islands in the middle of the Pacific (Howland, Palmayra, etc..). In the 1850s, people literally went batshit for guano. These uninhabited islands, while outside of any recognized territorial claim, were claimed by the United States in the Guano Islands Act of 1856. Because nobody disputed the claim, the U.S. kept them. Furthermore, that is now the basis on which the U.S. can claim a 200-mile limit, and protect the areas.
The island of New Moore in the straits between India and Bangladesh is more instructive. Here, the island formed in 1974, and triggered a land dispute between the two. A maritime commission had to be formed, and the matter wasn't settled when the island later disappeared beneath the surface.
Usually it would belong to a state whose national stepped to the new land first.