Accessories for Android devices with USB host
The cheapest way?  Use a µC with USB built in.  Many of the pic18 and upwards have this.  So do many other makes of µC.

The simplest way?  As you already state - convert it to RS-232 at TTL levels with some form of conversion chip like the FTDI.

Yes, there could well be problems with drivers for both solutions, but it is more likely the FTDI will be supported out of the box.  However, the first solution has the advantage that you can make the µC look like whatever device you want it to look like.

Oh, and as an aside - some of the high end PICs (eg some pic32 chips) have USB host built in as well.  Just thought I'd mention it...