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...
I'm no expert on Android but FTDI released an app note detailing how you can build in driver support for their USB to Serial IC's into the android kernel.
I don't know if this is feasible to do on a production phone, or if any phones have this driver already built in (I doubt it). In my opinion, Google has laid out a good specification for Open Accessory which will most likely be available on this generation of Android devices and the next given that they all update to the newer Android OS versions.
In the Open Accessory case, the phone switches over to a device and the accessory is the host. Implementing an embedded USB Host is a bit more complicated than using an FTDI USB to Serial IC but there are some pretty good application-specific micros out there that have hardware support for the USB stack and there are some examples out there of the Open Accessory protocol implemented on some of these micros. Given that the support is already in the OS for Open Accessory (or will be in the near future for all devices), I think this is the way to go.
Update: I switched this over to community wiki
It looks like Android is going to support USB Host in the kernel. Android 3.1 already has this, I think Android 2.4 will have it back ported, and surely Android 4 will have it. Therefore if you have a micro that can emulate an appropriate USB slave device, you should be able to communicate with Android fairly simply and cheaply as long as your Android device is hardware capable of USB Host. Most older devices (e.g. Droid, Droid Inc) are hardware capable, and new devices should be.
I don't know exactly which USB slave devices are easy to interact with from Android (here's a list of existing device types), but surely keyboard (i.e. HID) is an easy one to try.
Edit: The Android USB host APIs are based around the idea of having user-mode code contained within applications make raw USB transfers to peripherals. So instead of the "kernel driver" model, this is the "application understands peripheral details" one - conceptually very similar to desktop programs which use libusb or similar to talk to a peripheral. The exceptions would be HID devices such as keyboards and mice which Android talks to itself and utilizes in the expected fashion to provide input to the system in general. It's also worth noting that (with the exception of a few devices where the vendor has done otherwise) USB mass storage is not implemented by the system, so an app which wants to use such a device has to to implement both file system code and the USB mass storage protocol, against the raw android USB APIs.
There is an AVR library that provides a USB stack: http://fourwalledcubicle.com/LUFA.php. With this you should be able to do keyboard or other device emulation from a USB enabled AVR. Including this in your generic AVR firmware build is not too difficult. As Mihailo points out in the comments, make sure you use an oscillator frequency compatible with USB (8 or 16 MHz). I'm not sure whether it's possible to get this working on standard Arduino hardware.
It looks like the easiest way to approach this may be the new Arduino Leonardo board: http://arduino.cc/blog/2011/09/17/arduino-launches-new-products-in-maker-faire/
I'm sure cheaper/simpler/smaller Leonardo clones will come out soon, or roll your own!