Adding to tdc's answer, there are no known methods to compute exact estimates of the coefficients at any point in time with just constant time per iteration. However, there are some alternatives which are reasonable and interesting.
The first model to look at is the online learning setting. In this setting, the world first announces a value of x, your algorithm predicts a value for y, the world announces the true value y', and your algorithm suffers a loss l(y,y'). For this setting it is known that simple algorithms (gradient descent and exponentiated gradient, among others) achieve sublinear regret. This means that as you see more examples the number of extra mistakes your algorithm makes (when compared to the best possible linear predictor) does not grow with the number of examples. This works even in adversarial settings. There is a good paper explaining one popular strategy to prove these regret bounds. Shai Shalev-Schwartz's lecture notes are also useful.
There is an extension of the online learning setting called the bandit setting where your algorithm is only given a number representing how wrong it was (and no pointer to the right answer). Impressively, many results from online learning carry over to this setting, except here one is forced to explore as well as exploit, which leads to all sorts of interesting challenges.