Now, you said that this was not a fair argument because countries don't really "own" their land because they claimed it through violence etc, but I disagree. How else does one claim/own land (if not through violence)?
By acquiring it voluntarily or by homesteading an unowned resource. There's no violence in either case.
This goes back to John locke and Rousseau's ideas about property, but it is not possible for anyone to own anything without committing a "violence" against others. If one wishes to claim land/property he is necessarily impeding on the rights of others by saying that they cannot enter/use this property now, he is committing a "violence" against them.
This is false. Nobody's right is being violated there, if you're claiming unowned resources by mixing your labor to it. If nobody owned that resource, how could someone have their rights violated? Who was there before?
The homesteading principle minimizes conflicts. Any other alternative will either (1) increase conflicts, (2) end-up with a "cast society", where some have more rights than others or (3) follow the "universal communism" path, that I comment below.
Imagine a "state of nature" where everybody owned/shared everything (no property).
That's unfeasible. An ethical code that follows the "everybody owns everything equally" path would necessarily destroy mankind if followed rigorously. You wouldn't be allowed to do anything without consent from everybody else. You couldn't even use your own body (which wouldn't be yours btw, but equally shared by everybody else) without consent from others. But how would they even give their consent if they can't legitimately use their own bodies without consent from everybody?
You're asking good questions and you seem to have a much higher than average understanding. If you haven't already, I suggest you read Hoppe's texts on the ethics of private property. He can clearly explain what I'm writing here in much better words. A reading suggestion:
https://mises.org/daily/1646/The-Ethics-and-Economics-of-Private-Property The first man to "claim land" is directly impeding on the rights of others by taking their property/preventing them from "using" the land that they were once able to use.
You're wrongly assuming everybody else had a claim to the resource in question. There's no reason to assume that. You have no right to be able to use every resource available.
2. property, and thus taxation, is "just"
Property is just. But taxation, as done by practically every state in this world, is not. They'd have to be legitimate owners of the land they claim, what they obviously aren't.