Is it possible to build an iOS app that will get user's voicemails ? As I understand, such functionality isn't provided by iOS sdk. If so how such apps like "YouMail" are doing this ? This app is working with AT&T and this provider doesn't even have any API for getting voicemail..
These services, including Google Voice, allow redirecting the incoming calls to a special number if it is not answered, by sending that preference with GSM codes. That number provides the voicemail services.
What you are trying to do is impossible without setting up your own service that can accept the incoming calls on behalf of the user and getting the user to dial the GSM code to set up the call forwarding. This would require a pretty extensive setup and infrastructure and is likely impossible for your current needs.