Most startups don't have the resources to deal with the legal hassle of hiring an international candidate. However, if you have exceptional talent, you might be worth the extra hassle.
Try your luck applying to larger and more established startups (like Dropbox and AirBnB), they are more used to dealing with visa issues.