Get a degree. I've been in this situation (from the US to Canada), and having a degree helps. It's easy to have a company say they want you to work for them. The thing is, visa's aren't just approved because a company says they need you. They also need to demonstrate why they need "you" in particular, and why someone local can't help them. Why can't they hire an American, or a Canadian? Why are they hiring a foreigner? These are questions that need to be addressed. Having a degree goes toward helping demonstrate that.

To put it another way, I've never seen education shut doors for me. It has, however, given my opportunities I wouldn't have had otherwise.

It will be incredibly hard for you to get a visa without a degree. Damn near impossible, even. You DEFINITELY need a degree, especially if you're a foreigner and want to come to the United States. Very few companies, let alone startups, are going to hire you as an employee if you don't have a degree.

My advice would be to get a 4.0, get a degree, and try to go to graduate school at CMU/Boston/San Francisco area.

It's not going to be as simple as hopping on a plane and getting hired. You have a whole host of visa issues to work out, and if you do it incorrectly, you could jeopardize your chances of staying here long term forever.

I think that's the only way to get a visa that legally allows you to work in the US (ignoring visas associated with going to schools), but being a US native I don't know; as you say, you need to research that.

One thing I do know is that the last time I checked this year's quota of H-1B visas is not even close to being used up. Normally they're all used up on the first day which is sometime in April.