What kind of budget are you working with? I've had success getting through customer discovery and validating demand with adwords. Basically just drove ~$100-200 to a basic landing page and decided a 20% conversion rate was worth pursuing further.
I ask because there's a lot of opinion on what constitutes an MVP.