It's not because a class should only have one instance in a particular application that you have to use a singleton pattern. That is the key to solving this.
Simply only instantiating an instance of the class once and then passing it around to other classes needing it still maintains the singleton as a concept - only one instance - but does not have the disadvantage in the testing department and leads to nicer code in general because not everything depends on a singleton. To take this further, if needed, you can even make everything take an interface instead and also get rid of the dependency on a concrete implementation. Which in turn improves testability even more (depending on language and tools used, but most work better with interfaces). Suggested reading: Dependency Inversion, Inversion of Control.
In a small app passing around that instance can be done 'manually' via arguments. In large apps that becomes tedious and that is where Dependency Injection comes into the picture, implemented what is called an 'Inversion of Control' framework. It's abit much to go into detail here so check some tutorials on particular frameworks.
To give you a rough idea of how it solves your problem here is a sample for C# using MEF which I like personally because it uses attributes. First you don't need the static Instance method anymore. Furthermore you make it implement an interface. This results in code like
void NavigateTo( INavigable n );
[Export( typeof( INavigationManager) )]
class NavigationManager : INavigationManager
private readonly INavigationManager navMan;
DoSomeNavigating( INavigationManager navMan )
this.navMan = navMan;
public void Go( INavigable n )
navMan.NavigateTo( n );
First the testing: no dependency on NavigationManager itself anymore, and suppose you use the Moq mocking framework you'd write tests like
var navMan = new Mock<INavigationManager>();
var navigable = new Mock<INavigable>();
navMan.Setup( m => m.NavigateTo( navigable ) );
new DoSomeNavigating( navMan.Object ).Go( navigable.Object );
mock.VerifyAll(); //check that navMan.NavigateTo( navigable ) was called
When you need DoSomeNavigating in the application itself, you ask MEF to create an instance for you and have it automatically fetch an instance of NavigationManager. As the latter is marked with just Export, MEF knows it should should only create one instance of it so it takes care of the singleton concept for you. Since the first is marked with ImportingConstructor MEF knows it wants an instance of something which implements INavigationManager. Which in this case will be the NavigationManager instance.
var doNav = container.GetExportedValue<DoSomeNavigating>();