Sending the connection string to the service would not be a good idea. The caller should really have no idea if there is one database or one million (unless you are building something truly odd, like a database front end, along the lines of phpMyAdmin).
On the Entity Framework side of things, you can change the connection when your context is created. So, for example:
public class EFContext : DbContext
: base(DetermineConnection(), true)
private static DbConnection DetermineConnection()
// create an ADO.NET connection here based on your criteria
Which would leave open the connection of how to store/retrieve the connection. There are a few ways to handle this, beginning with the simplest (storing multiple connection strings in your web.config and pulling the one that applies to the current user) to more sophisticated methods (like putting all of your connection strings in an encrypted database).
Being the paranoid type, I would be more likely to do the latter.
The method that makes sense for authenticating a user (and, thereby having the information to determine which database connection to use) is mostly dependent on your setup. Some good links on setting this up with WCF would include:
Since you are using WCF, I would use Active Directory if it is at all feasible. Windows authentication tends to play very nicely with .NET security.