Any application whose primary concern is something with contact lists. Maybe it offers a special view into it. Maybe special searches. Maybe a better management interface.
An alternate phone or texting app
I can't imagine it would be difficult to implement a "Select All Contacts" functionality, in addition to selecting individual contacts and/or selecting all then deselecting some. Automatically allowing access to future contacts also shouldn't be difficult. There is no need for apps to always have access to all contacts.
I’m not sure how that would be functionally different than the current situation. Instead, simply regulating how contacts are allowed to be used would remove the need to build a logically complex system, and since Apple already reviews every app submission it would just be one more thing for a reviewer to check.