> I went for something even simpler: one new file Lib/test/test_tools.py.

I'm fine with this option too; if it grows too big we can always split it in several modules later.

> My only concern is communication: how do we tell people working on a
> tool that they should write a test in test_tools?

I don't think it's a big deal, eventually people will learn that it's there and we can always point to that file when a new issue is opened or during the patch review.
Adding a check to `make patchcheck` will also help (it's still better to add tests later than leaving the code untested), but maybe it should be displayed only if something is actually changed in the Tools dir (since that doesn't happen often, having always a "Tools modified... no" will just add noise to the output).