Hi Laureent,
I think, it’s possible by creating a custom field that hold the category id assigned to that entry.
As in EE more than one categories can be assigned to an entry but here in your case, it seems that channel entries will have only one category so the custom field will contain a number (category id) and this custom field name can be passed into orderby parameter of channel tag.
In this way your requirement can be fulfilled. you can think that it can be a manually process of updating checked category id into custom field. But it can be done with extension hook automatically.
I hope it would help you.
Best Regards,