Yes, this violates the GDPR if the user is in Europe.
Data which is tied to a personal device can be tied to the person who owns it. From "What Is Personal Data" by the UK Information Commissioner's Office (ICO) (emphasis added):
Personal data is information that relates to an identified or identifiable individual.
What identifies an individual could be as simple as a name or a number or could include other identifiers such as an IP address or a cookie identifier, or other factors.
If it is possible to identify an individual directly from the information you are processing, then that information may be personal data.
If you cannot directly identify an individual from that information, then you need to consider whether the individual is still identifiable. You should take into account the information you are processing together with all the means reasonably likely to be used by either you or any other person to identify that individual.
The bit about "all means reasonably likely" in the last bullet includes the kind of de-anonymisation tactics described in the NYT article.
There are 6 lawful bases for data processing in the GDPR, and all processing must fall under at least one of them.
(a) Consent: the individual has given clear consent for you to process their personal data for a specific purpose.
(b) Contract: the processing is necessary for a contract you have with the individual, or because they have asked you to take specific steps before entering into a contract.
(c) Legal obligation: the processing is necessary for you to comply with the law (not including contractual obligations).
(d) Vital interests: the processing is necessary to protect someone’s life.
(e) Public task: the processing is necessary for you to perform a task in the public interest or for your official functions, and the task or function has a clear basis in law.
(f) Legitimate interests: the processing is necessary for your legitimate interests or the legitimate interests of a third party, unless there is a good reason to protect the individual’s personal data which overrides those legitimate interests. (This cannot apply if you are a public authority processing data to perform your official tasks.)
Selling data isn't covered by any of the others, so consent must be obtained. Permission must be clear and positive, and you cannot predicate delivery of a service on the processing of data that isn't necessary for that service. So for instance you cannot say "You can use this service as long as we are allowed to collect and sell your data" because selling the data isn't necessary to the provision of the service. From "Consent" by the ICO:
Consent requires a positive opt-in. Don’t use pre-ticked boxes or any other method of default consent.
Explicit consent requires a very clear and specific statement of consent.
Keep your consent requests separate from other terms and conditions.
Be specific and ‘granular’ so that you get separate consent for separate things.
Vague or blanket consent is not enough.
- Avoid making consent to processing a precondition of a service.
This applies to any processing of data about individuals within the EU, so just being an American company doesn't get you a free pass to ignore the GDPR if your app gets used by Europeans.
The "Legitimate interests" basis is more problematic, in that the company collecting the data has to conduct a vague "balancing test" to determine if this basis applies. For direct marketing the ICO has written this, which says that direct marketing may be a legitimate interest, especially if you can show that the user has expressed interest in such adverts. For instance a location service which promises to tell you about nearby special offers would fall into this category. Against this, the impact on the user's privacy has to be considered, and location data is "special category data" because it can reveal medical information (e.g. hospital attendance) or religious affiliation (e.g. which church you go to). So unless the relationship between the recorded location data and the service is very direct its not going to pass the balancing test. The company would also need to distinguish between knowing the current location and keeping a record of historical locations; the two need separate justification.
And of course nothing about this covers the sale of the data; this is considering a company which sells advertising space in it's app, not one that sells the data itself.