Would this be possible with a Banshee plugin?
It's definitely possible.
Take a look at the current Last.fm extension / libraries. I think that most of the heavy lifting has already been done for you.
'/src/Libraries/Lastfm'
'/src/Libraries/Lastfm.Gui'
'/src/Extensions/Banshee.Lastfm'
Gabriel Burt (gabaug on IRC) would probably be the one to talk to about this.
~Mike