- recognize songs OTA (Over-The-Air), i.e. capture song by microphone and identify song
- be open-source
- work on Android
There is an app called "Encore" which is a fully featured music player with a lyrics finder and music recognition. It's free and open source, Here are the links to Github, GooglePlay and the xda forums thread.
Possibly one of the app's downsides is that you can't launch quickly the recognition activity with a widget (last time I checked) - you have to enter the app and go there manually. Perhaps, you can open an Issue on Github with this feature request and you will have exactly what you need.