I have created an initial version of a ListenBrainz plugin for Rhythmbox. Install instructions are on the plugin page. In order to use it you have to enable the plugin in Rhythmbox and then set your ListenBrainz user token in the plugin’s preferences.
The plugin will submit playing now and listened notifications to ListenBrainz. A missing feature currently is offline support, it will only submit listens if there is an online connection and otherwise drop the submission silently. I plan to add offline support as well.
On a related note the great Lollypop player also merged my patch to add ListenBrainz support recently. The next stable release should include it.