Provided you aren't trying to sell the game and are just giving it for free:
tl;dr: Upload everywhere. Keep track of where you uploaded. If Nintendo sends a C&D then take down those uploads like they tell you to do.
No matter what you do you are violating copyright law. That's just a fact of fan game development. If Nintendo wants to intervene, they can, no matter where it is published. They could even deal with it right now while it's just a couple of files on your hard drive if they wanted to now that you've expressed intent to publicly release. Because of this I wouldn't worry too much about releasing it wherever you want. In the end if Nintendo feels you are damaging the IP/their profits they will send you a C&D and maybe a couple of DMCAs to wherever you are hosting the game to get it taken down. All you'll legally be required to do is take down anything you've uploaded if the hosting website doesn't do it itself.
Google Play doesn't seem to have a review process so you won't be blocked before you can even get it to people. If somebody reports it for copyright violation they'll probably take it down. I don't know if they do anything else about copyright violations, but if it is a free app I don't see why they would bother. I think you'll be fine uploading it there. Alternative stores should be even easier and may even be less likely to get it removed due to user reports. If they don't have a submission review process you should have no problem getting it on their store. As for what alternative stores are out there I do not know. You'll probably have to research.
I'd also release the APK through Dropbox/MEGA/MediaFire/etc. and let people know about them as a backup.
If you are going to try to sell the game:
I think this is a really bad idea and you should rethink this.
Also I've not done this before. Everything in this post is theoretical. You should weigh your options carefully rather than blindly following any advise in a random forum post.
