In iOS 6 they added a new method to UINavigationController
that is retractively available in iOS 5 as well:
- (id)initWithNavigationBarClass:(Class)navigationBarClass
toolbarClass:(Class)toolbarClass;
Now you can just pass your custom class when the navigation controller is instantiated.