I have Google Voicemail, and it also requires a data connection to use the advanced features.
Unlike Google Voicemail, it's not as tightly integrated into the OS, so without a data connection you don't get an actual voicemail indicator. However, I have Google Voice send me an SMS notification when I receive a voicemail, which allows me to be aware of new voicemails even if my data connection is down.
Without a data connection, Google Voicemail works, well, pretty much like any voicemail. I can call my GV number and check it, just like checking voicemail on Verizon's system. There are prompts to listen to, skip, and delete voicemails.
So the answer is kinda yes and kinda no. Will Google or Visual Voicemail WORK without a data connection? Yes, absolutely. Will they work any better than Verizon's basic voicemail without a data connection? No, they're pretty much the same (especially after the next couple of days when the new Gingerbread version fixes the voicemail notifications on basic voicemail).
If you spend a lot of time in areas without data, don't bother with anything bust plain old basic voicemail.
If you're worried about missing a voicemail just in case you go into an area without data, don't. Verizon Visual VM uses native notification, and with Google Voice you just need to make sure to set things up so you're notified via a text message (which does not use data, SMS comes over the voice subsystem, not the data one).