How do you even do anything without using EBS?
Amazon certainly makes using EBS the easiest path. And EBS has a better reliability record as of late, but it's still often recommended to not use EBS. This avoids a single point of failure at the cost of a lot of complexity, though as AWS uses EBS internally, not using EBS may not save you if you use other AWS services like RDS or ELB.
If you don't want to use EBS, it's hard to know where to even start. A dilemma to which Kevin Nuckolls gives a great answer:
Well, you break your services out onto stateless and stateful machines. After that, you make sure that each of your stateful services is resilient to individual node failure. I prefer to believe that if you can't roll your entire infrastructure over to new nodes monthly then you're unprepared for the eventual outage of a stateful service.
Most databases have replication but you need to make sure that the characteristics of how the database handles a node failure are well understood. Worst case you use EBS, put your state on it, snapshot it regularly, and ship those snapshots to another region because when EBS fails it fails hard.
Also, logs make every machine stateful. Use something like logstash to centralize that state.
If ELB is down in a given region then DNS failover to another region. Assuming you feel comfortable rolling your entire infrastructure monthly, have good images / configuration management, and have the state replicated in the backup region. That or sidestep ELB in your region to a team of stateless load balancers that terminate SSL.
Jeremy Edberg to a question about how to run databases without EBS, says:
By having good replication, either hand rolled or built in.
At Netflix we use Cassandra and store all data on local instance storage. We don't use EBS for databases.