Update: today (2012) there is a much bigger tendency towards custom UIs, so I would say the answer below is way too harsh. There is still no supported way of customizing height, though, but you can certainly derive from UINavigationBar and override some sizing methods. This probably will not get you rejected (although it is still a grey area, just something Apple will probably overlook today).
Once you get the size you want, you can use iOS 5 customization APIs to add the custom background image (see WWDC 2011 Session 114 – Customizing the Appearance of UIKit Controls).
Original answer from 2009:
This is generally impossible.
What’s more, I believe making the navigation bar taller is a violation
of Apple Human Interface Guidelines, and your application may be
rejected from the App Store because of it. Please make sure your
client understands this risk before proceeding.(Pointing out rejection risks is usually a good way to convince
clients against making nonsense decisions.)