bluetooth headset with LCD and memory
I don't think you'll have any problems connecting it to the arduino.  As an example, you can look at the Sparkfun RN-52 breakout. https://www.sparkfun.com/products/11777  Even if it doesn't work out for you, you can look at their schematic and eagle files which might help you as well as the hookup guide.