easytag does allow to edit multiple tags at once. Just select all tracks which need to be changed. Then typ the genre you want in the corresponding field. Then press the little button right of the text field. this button will apply the changes to every file you have selected. Then save and you’re done.
JuK also supports editting multiple files, it’s not described very well though, basically you select the files and rightclick the column you want to edit (Genre, Artist, etc) and it will prompt you if you want to apply the changes to all the select files.
Amarok (comes with a default install) works the same way but it shows “Edit Album/Artis etc tag”. Also allows multiple changes from a dialog by selecting “Edit information for x tracks”.