Best Car stereo for my android phone
Check that the device supports A2DP and AVRCP.  You'll find many handsfree kits that connect to your stereo support those (it's what I use) - check out Parrot's range for examples.

Then you can use a separate mount and charger so that when you replace your phone you don't have to replace everything.