For the record, here's what I did...
Note: This is not for common situations, this kind of technique may tempt you to deviate from Apple's Human Interface Guidelines.
• A UIView was added on top of the UINavigationViewController
[[UIApplication sharedApplication].delegate.window addSubview:customView];
• Inside the new view, I placed a UINavigationBar, that was configured to look identical to the Navigation bar of the UINavigationViewController (including the back button!)
[navBar pushNavigationItem:item1 animated:NO]; // This item becomes the back button
[navBar pushNavigationItem:item2 animated:NO];
• Then you can animate the new navBar seamlessly