You can make an ad hoc ("on-the-go") playlist on the iPhone from whatever songs you have on the iPhone at the time. You can add songs to the on-the-go playlist one at a time or by artist, by album, etc. Just go to Playlists on your iPod and select On The Go and then make your picks and edit / save / cancel.
I find it ridiculous that you can't rename your on-the-go playlists from the iPhone. That always bugged me. The iPhone has a keyboard! Why can't we use it?