I spent most of last year in Cairns, Australia, making underwater videos of dive students, teaching underwater photography and renting digital cameras. I went there as a newly qualified dive instructor, couldn't get a job as a dive instructor (wrong time of year) and ended up being hired as a trainee video/photo pro. I had never used a video camera on the surface, let alone under the water. After three weeks of practising with the camera and shadowing the company's other videographers, I started making and selling souvenir videos.
So, you don't necessarily need a whole lot of experience to be an underwater videographer. You need to be somewhere where there's a market for underwater videos and you need to be able to live/work there. You need good people skills to get your customers to (1) perform for the camera and (2) buy the video afterwards, and also (3) to persuade the crew to help you out. You need to be self-reliant, confident and quick with your dive gear, and good with your buoyancy (you'll get much, much better). You need to be fit, because there's a lot of zooming round the ocean trying to get to the next shot. You need to be able to edit in-camera, because even if you're going to edit the footage afterwards (we didn't), you can save a lot of time by getting it nearly right the first time. You need to be able to adapt when the whole thing goes horribly wrong (because it will).
Most of all, you need to be able to live simply. As in cheaply. In a good week, I made about as much as a dive instructor... and that's not a whole lot. In a bad week, I made a lot less. I had a wonderful time, learnt a lot and will remember it for the rest of my life... but the overall impact on my bank balance was, hmm.... negative. If I look at it as a nine-month holiday with some work thrown in to offset the costs, it was good value. If I look at it as a job... ouch.
So, it isn't hard to be a videographer, you just need to be in the right place with the right skills. Making a career out of it is another story.
Z