I fly for AirLIb and I can assure you,
at CDG you are NOT allowed to use the RWYs of your choice!
If they have a westerly configuration like on the day of the accident (most common configuration BTW), then there is just no way you can ask for an eastbound departure; all you can do is make a request to change the overall rwy configuration, but unless a sufficient number of requests have been received, no configuration change will be done and all you can do is to eighter take-off from the unfavourable rwy after all or wait till sufficient requests have been made and the request are honoured by changing rwys.
As you can see from the weather at CDG that afternoon, chances were very high that no other plane would have requested an eastbound departure, which in effect would have ment the Concorde flight could have waited indefinitely! Remember the westbound departures are the preferred configuration in CDG as the city of Paris is to the west of the airport and they prefer high flying departing traffic rather then low flying landing traffic over their heads. Besides, a rwy change at CDG normally has consequences for Orly as well...
In short: you eighter go with the tailwind, or you don't go at all! So much as to a free choice of rwy which you are officially intitled to.