Best bet is to connect your iPhone to the computer you last synced to. You can go to your iPhone via iTunes and there should be an option to recover you iPhone to your last back up or sync.
Hey, we all know that method, but if users didn't sync iPHone to iTunes before, that means they didn't backup iPHone, your methods will not work, we need to way to restore files from iPhone directly without backup files.
Well then, I don't think there's a way.
I can't recall if videos go into Photostream, but you could check some of your iCloud services, possibly?
Otherwise, I'm not sure there's a way and the videos are probably lost. Good luck!