Arduino bluetooth module as a server
There are two types of bluetooth devices for Arduino. Some are "slave" only and some are both "master or slave". 

There is little difference in price so you should buy one that is master or slave.

This page (HC-05) describes one that appears to be commonly used but there are many and I do not have a recommendation. Some devices are in the form of small boards which connect to the pins on the Arduino (normally serial tx/rx) and some are shields that plug onto an Arduino. The article also shows the connection.

This appears to be an ODBII bluetooth arduino forum thread that uses bluetooth and ODBII. Video

By default Android is in bluetooth master mode. This article appears to show the Android programming required to enable a bluetooth slave.