How to allow some (non-admin) users to edit address/phone properties for all AD users?

I need to allow HR people to edit some attributes for all Active Directory users (phone numbers, address, and similar contact informations), without giving them full administrative rights. They will need the right to edit those attributes on all user accounts, regardless of the OU they're in, and this security setting should also be automatically applied to new user accounts when they are created.

How can I accomplish this?

You want to use the Delegate Permissions option in Active Directory Users and Computers. You can apply the delegation to whatever OU you want, including the domain root.

This will allow you to delegate whatever attribute-level permissions you want to whatever users/groups you define.

These permissions apply like any other and respect inheritance.

In ADUC, the Delegation of Control wizard will allow you to do this, using a custom task for delegation. Pick just the fields you want them to have Write access to.