RhythmBox is able to edit most, but I also need to override the default/downloaded image of the album art that's displayed when the song is played.
Please tell how to do so through RhythmBox (though I doubt that can be done).
If that's impossible, please recommend a few music editors/taggers that can get the job done.
Song metadata tags can be edited in Rhythmbox by right-clicking on the song and then selecting Properties from the popup menu. This will open a small Properties window in which you can select the Basic tab and edit the song's tags from there. However this way of editing tags is unnecessarily slow and repetitive if you are trying to edit the tags of multiple songs that have the same tags in some of their fields. If instead of Rhythmbox you use a music tag editor, you can batch edit the tags of multiple songs in a graphical application that is easier to use than Rhythmbox for editing tags.
EasyTAG would be a good GUI music tag editor to start with for three reasons:
It is easy to use.
You can edit (add or remove) album art.
You can batch edit the tags of multiple music files.
EasyTAG writes music metadata in a logical standardized way. There are two other music tag editors that offer you more freedom to choose the way you want to edit music tags: Ex Falso and MP3 Diags. All three of these applications can be installed from the Ubuntu Software Center.
Adding album-art to track metadata
Rhythmbox by itself does not have the ability to add pictures to the track metadata - you have the ability to change metadata such as title, album artist etc for supported file-types such as .mp3 but not covers.
You can use other apps like Picard and EasyTAG.
However, you can achieve what you wish straight from Rhythmbox via the CoverArt Browser plugin.
So how do I know this? Well I wrote the plugin...
Lets explain.
Sort out your album covers - you can drag and drop covers onto each album, or search for covers from Google or other internet providers
Then you can embed coverart:
At the same time you can optionally resize your coverart - for example you may not want a 2Mb cover being embedded in each and every album track!
This will save the album tracks in the folder location requested and each track in the album will have the coverart embedded in them.
You optionally can automatically convert to MP3 format.
Once you are happy you can copy back the newly updated tracks over your original tracks - or copy to whatever device/phone that requires your newly updated track covers.
If you wish to try this out, install the plugin via my PPA using the package
sudo apt-get install rhythmbox-plugin-coverart-browser
or install manually as described in the linked question & answer