One lawyer explains this like this:
Tokyo Metropolitan Police Department says:
In other words, a 15-year-old boy needs BOTH 保護者の許可/同意 AND 正当な理由 in order to go out late at night, regardless of whether they're alone or with their parents.
When a children is accompanied by their parents, obviously there is a 保護者の同意 indicated by the second clause. But it does not necessarily mean there is also a 通勤又は通学その他正当な理由 indicated by the first clause. Importantly, the first clause is independent of the second clause, and 正当な理由 in the first clause does not include 保護者の同意 itself. (Otherwise, 保護者の同意 would be the only requirement, and the first clause would be totally meaningless!)
As far as I could find, there are no official sites which states that the sole existence of 保護者の同意 serves as the 正当な理由 for a youth to go out late at night. Thus, even when a children is accompanied by their parents, it can be illegal depending on the situation. The lawyer I mentioned says:
In reality, basically you don't have to worry at all if you want to climb Mt. Fuji overnight with an underage child. But you will certainly be questioned by police officers when you are hanging around Roppongi with a youth late at night. Also note that many leisure facilities (such as theaters) absolutely deny entrance of underage people after 11PM even when they're with their parents.