Is it legal to update an Android app on the Play store with a totally different app under the same package name?
Is it considered against the policies since I am updating the app USING THE SAME PACKAGE NAME with a totally different app?
Is it legal to update an Android app on the Play store with a totally different app under the same package name?
well, there's no such definition "different app".
as long as you are using the same keystore (as @SplatFace Development said) it considers from Google play point of view the same app by definition.
you can change whatever you'd like.
it's legal for sure, and there's no any security problem with that because the user anyway would have to accept again the new app permissions if they changed at all...
and as I mentioned in the comment -
I almost sure google did it with thier own apps when Google Talk replaced with Hangouts.