what if Google simply Open Sourced the small amount of Android that isn't already Open Source? The Linux community would surely embrace it, integrate the bits not in the mainline kernel that should be, and move forward.
This only changes things if manufacturers start making 'empty' phones and require users to download and install their own free operating system.
Furthermore, many of the patents cover the phones themselves and not just the software. So even if some version of Android was 100% patent unencumbered, the phone manufacturers would still find themselves in "negotiations" with the patent cartel.