Jake of the Web

You don't need to have a Shazam! enabled iPhone to be able to find out the name and artist associated with a song:

Do you know how a song goes, but don't know the name of the song or the artist? Go to songtapper.com and tap the rhythm of the song on your space bar. Going off of just the rhythm, Songtapper can usually find any song you are looking for.
Song Tapper

Hum or sing a song into your microphone and midomi will tell you what it is.
Midomi

Tunatic will listen to music through your microphone, much like previously mentioned Shazam! and tell you what the song and artist are.
Tunatic