How can I download free apps without registering an Apple ID?
This is by design. Apple requires you to set up an account even for free purchases (except podcasts).

In the past, you could set up a free account in iCloud and get away with not entering information, but now the security is getting beefed up.

You may be asked for three security questions and to re-verify your account periodically. The passwords are now more strict in needing a mix of case and numbers where you used to be able to choose a simpler password for your Apple ID.

There are cases where the device is not working properly and you keep getting this verification error, but in the case you describe it is now mandatory to enter more information when setting up your account initially.