As far as I understand you can easily create new account if you have another account with EOS tokens on it.
Also there is a lot of online services that will help you to create first account for some fee. And they use their EOS account to do this.
But how first account was created without using existed EOS account?