You only need the ability to write to a file in your home directory. In the case of a VPS you could do that before editing the sshd config (in large environments this is trivially automated as part of your install process, which is why e.g. Ubuntu EC2 images ship with public-key-only SSH by default).

In the case of a shared server you can't disable password auth, which is a powerful argument for using a unique password since that system is far more likely to be compromised.