Context and Logic Answers
The context of the comparison in Romans 2 is between Jew and Gentile. The former are "under the law" and the latter "without the law" (v.12, ESV). Now consider the alternative you are questioning:
For when Gentiles, who do not have the law by nature, do what the law
While this is a true statement, and "would make sense" as well, it also is true of the Jew, and thus makes no distinguishing point if that was the meaning. That is, no one (Jew or Gentile) has "law" by nature, but rather by imposition or voluntary acceptance. The Jews were given the law, and willingly submitted themselves under the law (Exo 24:3; Dt 5:1-2; Josh 24:16-18), but "law" itself is not something natural and internal, but rather external, "the letter" written (Rom 2:27); something that needs to be "instructed from" (Rom 2:12).
So the contrast in Romans 2 is that the Jews had been given law, the Gentiles had not (v.12). But the Jews were failing to do the law even though they were not only instructed in it, but also teaching it (v.21-23, 25-27), yet the Gentiles "by nature" (i.e. out of an internal motivation of conscience, v.15) will at times "do what the law requires" (not always, but there are times "when" they do, v.14). When they do so, they are showing "the work of the law is written on their hearts." NOTE: the "law" itself is not written on their hearts, but the work that the law requires is so written in their conscience, such that some do not murder, commit adultery, etc., though they have not received a law from God that such is "wrong."
So it is the "doing" that is being "by nature," but this does not eliminate the fact that it is also a "status of the person," for one's works determine one's status (Rom 2:6-10), but the primary status shift between doing what is perceived as "good" (v.10) enough as opposed to "evil" (v.9) is not whether by law or nature, Jew or Gentile ways, as all are unrighteous (Rom 3:9-10). None are perfectly righteous as they need to be, except they go by the way of faith (Rom 3:21-30) to be accounted righteous (Rom 4:1-12).
So the chief "well-doing" (Rom 2:7) that makes one to do "good" (v.10) is to have faith in God, not one's own works, which gives one a status of "righteous," removing the status of "unrighteous," though both groups can do righteous and unrighteous individual actions, but none can do just righteous actions for every single action at all times, as is required to truly be righteous.
The picture set up in Romans 1-4 is that righteousness is binary: one either is, always, acting righteous; or one has but one failure, and thus becomes unrighteous. There is no middle zone, just shades of unrighteousness, but all shades are still not the white of right. Whether one is attempting to learn and follow the Law (the Jew), or naturally at times doing what the Law would require (the Gentile), neither gains the status they seek. The Law condemns the former (Rom 2:12), and the conscience of an individual condemns the latter when they fail themselves (Rom 2:15), and both will face judgment on what they do with the gospel message that speaks of the true salvation (Rom 2:16).
Greek Construction Helps, but Inference and Paralleling Answers
[This section is an update based upon Schuh's request in his answer for a Greek analysis.]
Breaking down the statement in Greek and translation:
(1) Ὅταν γὰρ ἔθνη τὰ μὴ νόμον ἔχοντα
When therefore Gentiles, the [ones] not law having (rough)
When therefore Gentiles, the [ones] having not law (smoothed)
by nature (left in a neutral position here)
(3) τὰ τοῦ νόμου ποιῇ
the [things] of the law they might be doing (rough)
they might be doing the [things] of the law (smoothed)
(4) οὗτοι νόμον μὴ ἔχοντες
these [Gentiles so doing] a law not having (rough)
these [Gentiles so doing], not having a law (smoothed)
(5) ἑαυτοῖς εἰσιν νόμος·
to themselves are a law
First, the participle phrase
τὰ μὴ νόμον ἔχοντα in (1), if the writer wanted to guarantee no ambiguity, could have included the adverbial modifier
φύσει ("by nature") between the article
τὰ and the participle itself
τὰ μὴ νόμον φύσει ἔχοντα. This was not done, though of itself that only hints that φύσει may not be intended to associate with ἔχοντα. The positioning afterwards does not guarantee no association.
Second, read the statement of v.14 without
φύσει ("by nature"). One would have this translation:
When therefore Gentiles, the [ones] having not law, ... the [things] of
the law they might be doing, these [Gentiles so doing], not having a
law, to themselves are a law.
Read that way, one is left asking the question "Why, or how, are they a law to themselves?" The correct inferred adverbial reply to that question would be "by nature," which is not left for one to infer, since it is explicitly stated (so that one does not answer "by chance" or something else).
Note how the construction above forms parallel concepts if
φύσει ("by nature") is grouped with the second thought:
(1) Not having law
(2 & 3) By nature do the law
(4) Not having law
(5) To themselves are a law
The "by nature" parallels "to themselves," or as a dative, could be translated "by themselves," meaning the idea of "self-doing" the law is what (5) explicitly states, which parallels (3) only if it is paired with (2).
Context, logic, hints from the grammatical construction, the need to supply an answer to a question arising from the statement itself, and the parallel thought construction all point to "by nature" referring to the working of the law without having had that law, not "by nature" being without law itself.