I don't think there are any solutions to this on a technical level. There's no way for you to prove that you own the domain, besides setting the NS-records.
You can partially mitigate the issue the way Amazon does it. But even that isn't foolproof and I suspect they have other reasons than just this for their approach.