The way I did it was I saved an XML file that was serialized from a POCO object that had the SQL Connection information into isolated storage. Since there are no real restrictions on the user account that can read and write from there, you don't have to worry about user permissions.
I then modified the settings events so that when the connection string property was read from the app settings file, I instead deserialized the XML file in isolated storage, built the connection string, and then put that into the app settings connection string property. Since I was doing this inside the settings class itself, I was able to write to it (but not save back to the file).
When my app runs, if it can't connect to the server I just pop up a window asking for the sql server info and they type it in and it saves it to the isolated storage, never to ask them for it again (even through upgrades).
If you have a client application (WPF or WinForms), users on other machines will not be able to use this and quite frankly you probably will not find a solution for that, unless you look into .Net Remoting or something of that nature. However, if you have multiple users on the SAME machine in a WinForms App, you can use the IsolatedStorage and it will work for all users.
In the settings class, add this event handler:
VB:
Private Sub MySettings_SettingsLoaded(ByVal sender As Object, ByVal e As System.Configuration.SettingsLoadedEventArgs) Handles Me.SettingsLoaded
Me.Item("MyAppConnectionString") = MyLibrary.BuildConnectionString()
End Sub
C#:
protected override void OnSettingsLoaded(object sender, System.Configuration.SettingsLoadedEventArgs e)
{
base.OnSettingsLoaded(sender, e);
this["MyAppConnectionString"] = MyLibrary.BuildConnectionString();
}