Anon1 has not let me off the hook yet, pointing out Gittin 40 where the gemara allows inheritors to fulfill their father's death bed instructions to free a shifcha. Isn’t this a violation of l’olam bahem ta’avodo? True, mitzva l’kayeim divrei hameis and fulfill a last request, but presumably not at the cost of violating an issur d’oraysa! Tosfos (38a d”h kol) answers that since the inheritors of the estate cannot use this eved for work because they are bound to fulfill the deathbed request of their father, there is no violation of freeing the slave. There are two possible ways to understand Tosfos' answer: most achronim understand Tosfos to mean that the father had already freed the slave with a verbal declaration, and that prevents the inheritors from using the slave; the children in this case are merely finalizing matters with a shtar shichrur, the formal emancipation contract. One could also possibly learn Tosfos as saying that the children cannot use the slave because of mitzvah l'kayeim divrei hameis; once the slave cannot be used for work, the prohibition of l'olam bahem ta'avodu categorically no longer applies (this possibility is raised in the Rashba). Does being blocked from enjoying the labor of a slave automatically give license to grant freedom - is the issur fundementally designed to preserve the slave's burden of labor, which in this case is inapplicable, or designed to maintain the status of servitude, which applies irrespective of the burden of work? Be that as it may, as Anon1 pointed out, the Rashba offers an alternative answer more in line with the Ramban’s approach to the whole sugya. The issur of emancipating a slave applies only if freedom is granted as a free gift with nothing received in return. In the gemara’s case, the freedom was in exchange for the great benefit the slave had given the master during his lifetime.
Minyan l’inyan: according to many meforshim, Eliezer served as the shliach of either Avraham or Yitzchak to be mekadeish Rivka, and although an eved is pasul for shlichus of gittin and kiddushin, Eliezer (based on Pirkei d’Rabbi Eliezer) was freed for the mission. One can use some combination of the above sevaros to how Avraham (or Yitzchak) could do that without violating any issur.