Terry, i guess you are right; it is indeed not the job of python to know how its terminal will print characters; there is a whole lot of issues to consider, such as terminal unicode support, control characters, ansi escape sequences, terminal-specific escape sequences such as terminal title, etc.
I guess that on UNIX, a lot of that information could be taken from terminfo, to provide a method that guesses the length of a text on the terminal that is referenced in the $TERM environment variable.

In fact, I think this is a design problem of readline; readline should print the prompt, and then try to determine its length via the dedicated escape sequence (if it really needs to know the prompt length). In that case, there would be no way to fix this in python - apart from re-implementing. In conclusion, no, I don't believe the python readline code should be modified, maybe an additional, os- and $TERM-dependent method for adding prompt escapes should be added.

However, the issue should definitely be documented in the readline documentation:
importing readline _will_ break input() if the prompt contains non-printable characters that are not escaped by '\x01' and '\x02' characters.

Hence I have changed the bug components to 'Documentation'.