The Markov stuff seems like such a poor approach. Though you can get by with it in 140 characters better than other places.

Twitter provides a public stream of tweets. Simply pull tweets out of that, if it doesn't contain another users name or url, etc. Distribute out to one of your bots, weighted by chattiness. Get fancy and have some sort of baysian filtering for what category bucket it falls into and give your bots interests.