Simplest Way to Connect an Arduino to Android (Wirelessly)?
Option A is feasible, but non-trivial.

Option B: Without using Bluetooth, there isn't any ready wireless radio serial output that  any Android phones have, to my knowledge. 

There is an option C, if the requirement is relatively close range, and purely for hobby experimentation:


Programmatically generate a ~ 19-20 KHz audio output from the Android's speaker, at maximum volume - Most adults can not hear such a frequency, but my android phones can all emit up to 22.1 KHz successfully.
Implement a basic electret microphone --> preamplifier --> narrow bandpass filter --> peak detector using op-amps, with the pass-band at the frequency of interest.
Use an Arduino ADC pin to sense signal from the above module.


Some simple enhancements:


Use two different frequencies, such as 18 KHz and 20 KHz, pulsed alternately, and detect for such an alternating sound input at the Arduino end. This will avoid spurious false-positives.
Use a slightly wider band and skip the peak detector, use the Arduino to sample and process the incoming audio signal to detect specific frequencies received. This latter adds the flexibility of changing design frequencies or achieving more complex signaling through Dual-tone-multi-frequency (DTMF) protocols, similar to touch tone phone dialing, or Frequency Shift Keying as used in old dial-up telephone line modems. 


There are several Android apps which use such sound signaling for various purposes. Also, this slideshow proposes a similar mechanism, for transfer of data between Android phones using sound.



UPDATE: This question about Infrared audio transmission / reception between mobile phones, brings up an interesting Option D, that of using an infrared transmitter connected to the audio out of the transmitting cellphone, and using a standard infrared sensor as a receptor on the Arduino. The rest of the mechanism remains as in Option C, with the preamplifier, band-pass filter and so on.