Is there a way to let every user can choose (e.g. on registration) whether their field is private or public?
If you want to do this without writing any custom code, you could use Panels.

Create a boolean field, Show my address publicly, and add it to the user profile.

Then override the user profile display with Panels.  Add all of the fields that you want to display, including the address field.  Then, add a Visibility rule to the address field and set the condition to be Show my address publicly == TRUE.

This is a bit complicated to set up if toggling the display of the address is all you want to do, but Panels offers a lot of flexibility (without writing code) that could be used for other things, too.