MySql - alternate of auto_increment on multiple columns
You could use a trigger.  The key problem there though is that it will have to do a lookup and so multiple concurrent inserts into the table may get messy (concurrent being within the life of the transaction).

A real alternative here is probably going to go with a natural candidate key (multiple columns of actual rather than artificial data) and add a single autoincrement key for easy joins.  Having a single column reference makes joins to the table a lot easier.

Those probably aren't the answers you want to hear but they should work.  If they won't work, then the question is why and what data modelling scenario you are trying to address.