If you've got a Mac, downloading YouTube to Mac, converting them to iPhone friendly format with freeware, and then uploading them to iPhone with an app like VideoSafe over the Mac's WiFi isn't that difficult.
This is incorrect. There are still several apps out there that are capable of downloading things and saving them onto your iPhone. I use Downloads. You may also try Downloads Lite. The only difference is that the free lite version limits your downloads to 10 while the paid version ($1.99) is unlimited. I just saved a YouTube video by going to their website, finding a video, holding on the text for the prompt, and selecting download. Best of all, this does not require any sort of jailbreaking and is available in the app store. Try it.