Is the database encrypted?
If it's not something that requires a large amount of privacy, you can store the connection string on a per-user basis.
For example:
System.Properties.Default.MyConnectionString = "Blah";
System.Properties.Default.Save();
or
string myConnectionString = System.Properties.Default.MyConnectionString;
EDIT: These can originally be set in VS by going to Project -> Properties -> Settings and make sure you put them in "User" Scope (Application Scope is read-only during runtime unless I'm mistaken).
EDIT2: Regarding comment below:
SqlConnection myConnection = new SqlConnection();
//Set from a normal String saved in user's settings
myConnection.ConnectionString = System.Properties.Default.MyConnectionString;
myConnection.Open();