In any case, OpenJDK was released in May 2007, and Android unveiled in November later that year and made available only a year later. The reason Google used Apache Harmony was because they couldn't reach a licensing agreement with Sun and chose not to use OpenJDK because of its GPL license, believing phone vendors would reject it.
As Google probably wanted to have a non-standard edition of Java, it's unlikely that Sun would have licensed it to them (or they would have required a new standard being formalized first). Their best option was to use OpenJDK, but they didn't. They wrote their own runtime -- which, to this day, is at a great performance disadvantage compared to OpenJDK -- suffers annoying incompatibilities and is a few Java versions behind, all in order to not use GPL software.
Was Google right in thinking that phone manufacturers not have put up with GPL? I'm sure that at the time that's what the phone makers told them. Perhaps Android wouldn't have taken off if they had tried to shove the GPL down their throats. But I believe that with the iPhone breathing down their necks and no better alternative, the phone vendors would have yielded. We would have ended up not only with a much better, faster, more compatible Android, but with the most ubiquitous operating system on the planet being truly free. This also would have prevented the Oracle-Google lawsuit.
Instead, we're left with a slow OS that's years behind embedded Java, not truly open (as closed-source modifications are made by vendors), and a legal battle that some believe may have far-reaching consequences. All because people are afraid of the GPL.
[1]: For example, I believe (though I'm not sure) that IBM's and Aicas's JDKs follow the first choice (maybe the second), Azul's Zing JVM the second, and Azul's Zulu the third.