This can be done through the standard Magento promotion rules.
Go to Promotions->Shopping Cart Price Rules.
Try to create new rule and Fill the relevant information for your rule in the first tab.
In the conditions tab click on the green plus by following the below structure:
If ALL of these conditions are TRUE :
If an item is FOUND in the cart with ALL of these conditions true:
SKU equals or greater than 2
Attribute " Shoe type " is assigned
Now under actions tab fill the relevant information and save.
Then go to frontend and add 2 different products having the attribute "Shoe Type" assigned.
Apply your coupon code and it should work.
It worked for me.