There were banks before the FDIC and people trusted them. The threat of insolvency can (but doesn't always) keep them honest.
AFAIK any of the online banks could be running out of a hole in the wall in Ukraine or Nigeria. Even paying online sites with credit cards is risky these days with the rampant fraud etc, I wouldn't trust anything online only enough to entrust my money unless backed by a big player.
That's part of how the market solves this sort of problem, traditionally. When trustworthiness is especially valuable, brands develop that have it. One way to bootstrap the process is to start with an existing brand that has it, like American Express. Companies that want to be seen as trustworthy can also do things like offering money-back guarantees and putting money aside in an escrow account held by a third party.