Я бы просто создал экземпляр UINavigationController прямо перед тем, как вы представите свой модал.
YourViewController *modalViewController = [[YourViewController alloc] initWithNibName:@"foo" bundle:nil]
UINavigationController *tmpNavController = [[UINavigationController alloc] initWithRootViewController:modalViewController];
[modalViewController release];
[self.navigationController presentModalViewController:tmpNavController animated:YES];
[tmpNavController release];
Это просто конец конверта - я бы не копировал и не вставлял этот код без двойной проверки!