Here is a patch that backdates outputs 1s after their youngest input (and sleeps if necessary to avoid producing files in the future).

With that, I get

lap-le:3k loewis$ touch Parser/asdl_c.py ;date;make touch;date
Mo 30 Sep 2013 15:29:21 CEST
hg --config extensions.touch=Tools/hg/hgtouch.py touch -v
Touching Include/Python-ast.h
Touching Python/Python-ast.c
Mo 30 Sep 2013 15:29:23 CEST
lap-le:3k loewis$ ls -lT Parser/asdl_c.py Include/Python-ast.h Python/Python-ast.c
-rw-r--r--  1 loewis  admin   19489 30 Sep 15:29:22 2013 Include/Python-ast.h
-rwxr-xr-x  1 loewis  admin   43732 30 Sep 15:29:21 2013 Parser/asdl_c.py
-rw-r--r--  1 loewis  admin  228785 30 Sep 15:29:23 2013 Python/Python-ast.c

BTW, I think the Python-ast.c issue could be solved by just having Python-ast.c depend on the same inputs as Python-ast.h; the C file isn't actually depending on the H file.