Bei Samsung ist auch schon eins drin, soweit ich weiß. Bei O2 gibts einen dienst dafür, dessen Namen ich grad nicht weiß, der kostet allerdings auch was, kommt per SMS.
Shazam und / oder Midomi sollten eigentlich auf so ziemlich jedem Smartphone funktionieren.
PS: Kostenlos ist das auch nur wenn du eine Datenflat hast.