You can do that using "smart playlists". I have a playlist that contains all my 4/5-star rated songs, a playlist that contains the 250 most recently added songs (you can adjust the number of songs here to accommodate your available memory), and a static "iphone" playlist. I have set iTunes to sync only these playlists. This way I always have the recently acquired stuff and my favorites on there, and also can add stuff manually by putting it into the "iphone" playlist.
Can this be done on the phone, with iTunes in the cloud? I never (rarely) sync with iTunes.