You could simply use the “pods”-plugin (for WordPress) from Matt Gibs and Scott Kingsley Clark. It’s exactly what you searching for. Take a look at the doku and look specificaly at “pick columns”. Aside from that it has a nice and ajax driven interface and builds it’s database tables next to wordpress and doesn’t make use of the default tables (there’s nothing wrong with adding new tables). It really converts WordPress to a full CMS system. I tried it in some projects and was easily able to achieve everything i wanted. A big plus is the irc-chat where you find a nice, friendly and helpful croud and the developers. An here goes another plus: When you feel comfortable with pods, then add pods UI to your weaponary. 🙂
Wish you best!