If it's the pre-installed phone app on your phone you can't uninstall it, but uninstalling updates is possible if those were received via the play store. This will take you back to the most recent version installed by a system update (not the original version that came with the phone).
What will happen to data? I know nothing about visual voicemail, which is a carrier-specific feature, but it will do nothing at all to contacts (which aren't owned by the phone app) and I don't think it will do anything to call logs (which can be accessed by any dialer, so can't be owned by the system phone app). Call logs are easy to back up anyway (e.g. the widely-used SMS Backup and Restore also backs up call logs).