Google should start a patent pool with all of their patents. Every company would be granted full license to use these patents, as long as they commit not to sue anyone else (in or out of the pool) for patent infringement. Ideally, they would commit their own patents to the pool as well.
With enough buy-in, this could effectively null out software patents without any legislative change, at least among non-trolls, since with a large enough pool it would be almost guaranteed that a company would violate more patents in the pool than vice-versa.
Ideally, this pool would be managed by a non-profit institution, patents would be committed irrevocably, and the organization would have lawyers to actually sue any other company that filed a patent lawsuit. This may be similar to what's been done for WebM etc., but it seems like the same idea on this much larger scale could be much more powerful.
Main challenges I could see are (1) patent trolls, since there's nothing to sue them for, and (2) who decides what's a software patent -- not sure how clear-cut of a line this is.