So it's not whether Android allows that but whether Google's Play Store conditions allow that. As I've never submitted an app to them I've never had the need to go through their conditions in detail, so can't help with that.
Certainly apps can access the contacts data and write them out (backup apps do this), so I don't see that storing their own copy should be more of an issue. After all, they are the user's data, not Google's, so as long as you make clear what you are doing in advance I don't see rationally that it would be Google's problem (of course as a user I would like to know what you are doing with the data before I install the app or give you access, but that's true regardless). However what's reasonable and what's in the Play Store rules are not always the same thing, so I'd suggest reading in detail.