I think something like this should work:
rule lint-check
command = $pyflakes $in && touch $out
build file.py.checked: lint-check file.py
default file.py.checked
Your idea, "is this file newer than the last time I ran this command?" is interesting. It mostly makes sense but you need some way to tell Ninja that it ought to consider running the command (which my above "default" does, by using an explicit path to represent whether the command was run).
This is actually very related to what I've been thinking about for Ninja v2. Ninja already actually tracks when a command was run. If there was some way to express a no-output rule (like lint-check) and still pull it in as a dependency (which currently only works as files) you could express your goal in a more ideal way, without the extra "checked" file. That still leaves the question of why Ninja should know to run the command, if you didn't ask for it, though..
(Sorry for the confusing paragraph, just thinking aloud.)