You can replace the TCU in your 2004 with the TCU from a 2005, which will allow you to have Bluetooth and retain Assist. Review this TSB -
http://www.bmwmotorsports.org/pdf/841304.pdf
The part number they gave you is what you need to do this. The vehicle will need to be recoded at the BMW dealer after the new TCU is installed, as referenced in the TSB linked above.
As for a phone, the Motorola V710 works fine with the 2005 TCU and there is a docking cradle for this phone. Note that you will need to install a second antenna in the vehicle if you want to use the cradle, as the antenna that is installed in the vehicle is being used by Assist.
Jeff