Yes it is definitely possible, but not easy, since the INS is as incompetent as they get. However, the brief overview that you have given does not contain all the details required. First of all, have you graduated yet? If yes, then it seems that you should be able to use your OPT until then, and can continue to work on the startup. However, on OPT you cannot receive ownership of any company stock and as such have to be excluded. You are free to work, but not free to own. The company can pay you some salary, provided it has the ability to do that. The rules could be murky here, but as far I understand it, my lawyer expressly stated that I should not own any shares before obtaining my visa. (Although my visa category was an E2 investment visa, which is a different designation)
For your company to sponsor you for an H1 visa, it needs to be able to show that it has considerable financial resources (either revenue, or investors). So if in a year from you have a LOI from an investor or revenue, you can show that to the INS for credibility.
As far as the incorporation goes, I think initially its best to have it as a partnership LLC, since it is pretty flexible and gives you enough wriggle room since LLC's are often open-ended and can be structured in a variety of different ways. Once you go big, have your H1B you can think of shifting towards another incorporation model, as most investors would want you to anyways.
IF you have not graduated, then best advice: take a min number of credits while in school and work on the startup till you get decent sized enough that you can attract funding or have enough revenue to get an H1B or an E2 investor visa.
Hope that helps. I know how hard these immigration issues are to wrap ones head around, so let me know if you have any more questions. I have been through it.
There is also a great blog post written by one of the principals at K9 ventures. I suggest reading all of his stuff on visa issues as well: http://bit.ly/nTsGTy (its a text only version since actual page is not loading)