According to the docs, if you assign a non-string object to sys.ps1 then it will evaluate the str function of it each time:
If a non-string object is assigned to either variable, its str() is
  re-evaluated each time the interpreter prepares to read a new
  interactive command; this can be used to implement a dynamic prompt.
Well now it's obvious, you should make it dynamic! Make an object with a __str__ method where you can place any logic you want:
class Prompt:
    def __str__(self):
        # Logic to randomly determine string
        return string
You can also make changes or insert things into this class as you go too. So for example, you could have a list of messages in Prompt that you append to, or change, and that will affect the console message.