The Arduino Micro, announced just yesterday by AdaFruit and Arduino, might be a good solution for you.
The new board is compatible with the Arduino Leonardo and uses the ATmega32u4, thus it comes with built-in USB functionality. The size is 1.9 x 0.7 inches (48 x 18mm), with a microUSB socket at one end.
Note that this board is different from, and actually bigger than, the SparkFun Pro Micro, which is a mere 1.3 x 0.7 inches and also comes with the same MCU and USB functionality - so I'm not quite sure why the Adafruit product was announced at all.
A power source and an equally tiny Bluetooth module (e.g. 1, 2, 3, 4) would be needed, and of course the functionality required will have to be coded.
Before going down that path, this other question is a valuable caution about 3.3 Volts v/s 5 Volts in connecting up a module to any 5 Volt Arduino.
There are also several other, older Arduino boards of various diminutive sizes, such as the unbelievably tiny yet fully capable FemtoDuino at 0.81 x 0.6 inches (20.7 × 15.2 mm). However, these require USB to TTL conversion either using a FTDI chip or otherwise. None of the various ultra-tiny Arduinos seem to support USB natively, but searching deeper might prove otherwise.