You can buy a SIM card in a vending machine in at least airports in Denmark and the UK.
Because I've seen SIM cards that can be bought in supermarkets in another country, but then you need to show your ID to an operator over Skype to activate it.
I am willing to bet the vast majority of European countries will follow suit before 5 years though.
1- Use the new "anonymous" sim card with a phone you already own and used with other sim card (IMEI matching).
2- Use a new phone with the new sim card but let it connect through your home WiFi network (IP tracking).
3- Use a new sim card and a new phone, but carry the new phone around with your main phone so that they find your second phone and number just by looking in the carrier(s) database(s) if there are any matches to the tower areas the first phone connects to.