I don't know whether the decision to use a Linux kernel for Android was made at Android, Inc or later at Google, but it's pretty clear that Google wanted Linux.
I suppose at the time, the whole Linux mobile thing had already generated a sufficient amount of traction so that a lot of the necessary infrastructure was already there.
I was working for a mobile phone manufacturer at the time (that was later acquired and shut down by BenQ) and for us, the successor to Symbian would have been Linux, too, built along the Opie and Qtopia userlands on Texas Instruments OMAP hardware. Both Google and Trolltech had offices in the city (Munich). At that time, Google was still developing its products as J2ME software though.