I've published games where I released updates with additional levels, so I don't see that a story-based game is necessarily different. However, I'd avoid describing the game as unfinished in any way (maybe "episodic" or "continuing" would present it more as a feature). Aside from the marketing aspect, it would be less risky, rejection-wise. I once got an App Store rejection because the description had the word "sample" in it, even though I was referring to another project that I was crediting. Google Play may be less strict, but in my experience even there paid apps seem to get more review scrutiny than free ones, and when I've had a rejection it was a real hassle figuring out exactly what their objection was and even how to respond.