How feasible is it to test a business idea using only free-tier services?

Depending on what it is, I think it's extremely feasible.

If you're offering some sort of client services (w/o a product component) you could very well stand up a website on Gitlab pages for free and call it a day.

Depending on the availability of an app offering, could very well use the Heroku free tier with some success.

Not quite 0$ but I've run fairly profitable sites off of 5$/month VPS hosting.... all about how good you are at caching :P