I travel this way quite a bit. I'd recommend finding a flight in, a flight out, a starting point, and that's it. Don't buy or plan anything much in advance. If you're traveling on a budget, it may not be worth it to bother with a no-foreign-transaction fee credit card. Lots of places in Europe are still cash-only, so reimbursal of ATM fees is more worthwhile than 3% on a couple grand. Go to your starting city, go to your hostel, and start making friends. Wander about at will. Your new friends will also be travelers, and since they will probably be European, they will know of some beach somewhere they are going to next and wouldn't you like to come along? Of course you would! That sounds awesome!
Bring a backpack, don't bring a bunch of luggage. It will just slow you down. You don't need much, just a sense of adventure. Don't buy train tickets in advance. They are more expensive that way, oddly, and it's just unnecessary and it locks you in.
I like traveling in and out of Heathrow (cheapest for me, see friends in London) or Charles de Gaulle (get right on a train), but it doesn't matter much, just do whatever is best for getting back and forth to your home city. It might be worth it to have a flexible ticket if you have flexibility about your return date, but naturally those are more expensive. If you buy with miles you *can* have more flexibility. RyanAir sucks, I prefer EasyJet. But beware of the insane fees the discounters like to pile on for everything.
GET TRAVEL INSURANCE. It's super cheap and it's worth it.
Traveling this way, you probably won't get the whirlwind tour of capitol cities experience, but so what? You'll have a great time, a unique experience, and at another point in life you can easily pick a city, spend a week there, go home, rinse and repeat. I wouldn't bother with packaged tours. You can always get a day tour in a city if you want. Or you could just go with one of your new friends to get lunch and then check out that museum over there. Friends are key to the solo traveler, and then you have a friend to visit next time you head over!
Bon voyage!