Unfortunately, you must upgrade an existing installation before you are able to do a clean install of Windows 10. It is only once an upgrade has been done that you have a Windows 10 license at all.
After an upgrade has been performed that PC is licensed to use Windows 10 and a clean install can be done. During the clean install the product key entry should be skipped (multiple times if required) - the PC will still automatically activate when installation is complete.
From what I understand Windows considers the motherboard to be the PC for the purposes of licensing, as long as the motherboard is the same the PC is licensed for Windows 10
For more detailed information on performing a clean install, see this article.
In light of some of the confusion around this it's worth pointing out that although a lot of the Windows 10 licensing messaging has been unclear, the upgrade first requirement for clean installs has been something Microsoft have been talking about for as long as they have been talking of Windows 10 clean installs - so the system is "working as intended". It is, of course, entirely possible that Microsoft will create a new system for this soon, but for now this appears to be the only option.
Note that currently some people are having trouble activating Windows 10 despite having legitimate versions - these problems seem to resolve themselves in time
Edit: Removed unnecessary information about retrieving product keys