Voicemail app that doesn't require carrier voicemail
Try if any of these apps work for you. It would depend on your phone, as android has limited support for total offline answering machine capabilities due to technical barriers. See this thread on XDA. If your phone isn't compatible, you might have the following issues:


Not be able to record calls
Record the conversation at only one end
Very low sound quality or volume


Google voice doesn't depend on your voicemail. The calls are recorded on google voice's servers.