Create relation N:N and specify properties for each relation
If there is an existing contrib module for that, that would be Relation. It works at the level of Entities. It should provide a generic API/framework that can be used for what you describe.

If Relation doesn't fit your needs or is not ready for you, then writing a custom module would be the only option. For a custom module, I would work at the Entities level (with the help of the Entity API module), not directly in SQL. While Drupal doesn't provides scaffolding for Entities, it provide helper functions such as field_attach_form() or field_attach_insert() to deal with fields on entities. Unfortunately, the documentation on how to properly use entities is still scarce. The Model module is an attempt to help there since it aims to provide a model entity and entity administration interface to kick-start your entity development.