Just so everyone is clear, Android ICS 4.0.4 doesn't have AVRCP 1.3 support. It's not the Android application for Spotify that is the real culprit here. There are some custom ROMs that have AVRCP 1.3, you can install those and have it work fine.
Bluetooth on iOS supports AVRCP 1.3, which is why it works there.
Samsung do provide AVRCP 1.3 support on their Galaxy S2 and S3. Track titles and artist display fine using the stock music player, but yet to find a streaming player that does this? Except if you buy an iPhone of course!
lawrencealan, I'm not sure where you got your info, but I have a droid razr ( android 4.0.4); specs indicate it supports AVRCP 1.4. Google music streams with full track info, which is a solid indicator that the bluetooth stack is capable of streaming meta data.
Pandora and spotify do not stream meta data. I have to think this is an app issue, not an os issue. I guess since each phone has vendor specific wireless hardware , different bluetooth stack implementations are out there .. perhaps there are some ics phones out there with older bluetooth stacks, but I don't think the android version can be tied to the AVRCP support carte blanche.