I assume that using a time stamp authority is done by the person signing the message, and that in order to use one then the computer that holds the private key must be connected to the Internet.
There are a couple of different ways to do it, but what you describe is one way. Yes you're right holding a private key online is generally a bad idea, but thats what most "authorities" such as certificate authorities that sign SSL keys do, and even SSL keys themselves must be kept online. Another way is for the timestamp authority to publish random numbers at a regular interval and have the client include the latest random number in the metadata.
It would be cool to implement something that used a blockchain as a timestamp authority.
you could include the hash of the most recent found block. Unless you are willing to withhold a block for a long time (and obviously control enough hashrate to find blocks often enough to pull this off) then it would prove that you signed a message on or after the time the block was found.