Part of this puzzle is missing, realizing that Gio.MenuItems themselves have attribute values.
So, in this case, before adding a menu item to GMenu, the syntax is required:
item.set_attribute_value("accel", GLib.Variant("s", "<Alt>Z"))
To fulfill the answer, you can also set the shortcut and action for the menu item as follows:
item = Gio.MenuItem ()
item.set_attribute_value ("label", GLib.Variant ("s", "RandomAlbum"))
item.set_attribute_value ("action", GLib.Variant ("s", "app." + action_name))
However, the set_label and set_detailed_action do the same.
source share