This is the sequence and timeline. I've underlined the dates of which I am confident enough, that I use them to constrain other suras.
56, 86 before 77.
54, 77 before 69 (< 648).
73 after 30, 54; before 17.
17 after 73; before 10 - in Palestine (mid 630s).
99 also in Palestine (mid 630s).
55, 82 before 83.
10 after 17, 80, 99; before 3 (640ish).
3 after the muhammad's death.
69 reacting to the storm (648ish).
6 announcing 'Uthman's codex (early 650s)
8 after 6, before 4 and during the fitna (656)
20 after 10; before 7 (< 680).
53-final after 6, before 7 and 12 (650-80).
18 during the Furqa (657-60).
7 after 18 and 53-final, before 36 (657-80).
11 after 7, before 13 and 14 and 67 (657-80).
5 after 4, before 13 and 22 (657-685ish).
59 after 5,7,8; before 41 (657-90).
36 after 7, 18; before 67 (660-80).
71 against Yazid (680ish).
78 also.
13 for Yazid or Abd al-Malik (680ish or 685ish).
14 by Ibn al-Zubayr (680ish).
67 for the Dome (685ish).
22 also by Ibn al-Zubayr (685ish).
41 after 13 and 67, against the Zubayrids; before 25-28 (late 680s).
34 after 22 and 41; before 25 (690ish).
74 between 14 and 25 (685-97).
76 between 22 and 74, and 25 (685-97).
25 after 34 and 74 and (maybe) 76; before 45 and 26 - the Furqan (690-700).
45 after 25; before 27 and 85.
85 after 45 and 67 (690ish).
12 in Egypt under 'Abd al-'Aziz (685ish).
26 after 14, against al-Hajjaj (695ish-700).
27 between Sulayman's governorship and Yazid b Muhallab's arrest (695ish-709, likely before 700).
81 between 26 and 37.
37 between 27 and 28.
28 between 37, and 32 and 39, against al-Hajjaj (695ish-710, likely before 705).
19 after sura 28 and before 21 and 32 (695-705).
32 al-Hajjaj, between 28 and 16 (700-710)
2 after Ibn al-Zubayr, before Walid's Mosque (680-705).
65 between 2 and 66 (680-720).
39 between 38 and 21 (695-710).
57 either 'Abd al-Malik or Walid (695-715).
21 either 'Abd al-Malik or Walid (705).
51 against 21, before 52 (705-715).
52 between 51 and 68.
68 between 52 and 70.
29 after 2, 21, 31 but not knowing 51 (> 713).
42 after 29, 68; before 23.
70 between 68 and 23 (705-715).
60 between 29 and 9 (> 705).
49 after 52, 60.
23 after 42, 70; before 43, 72 (705-715).
72 after 23, before 40.
43 after 23; before 40 (715-20).
40 after 43, 72; before 16 (718ish).
16 between 40 and 35 (> 718).
9 between 16, 60, and the Dome's plaque; and 61 and 66 (> 718).
44 by an an anonymous Kindi in Kufa (730ish).
35 between 16 and 46 (> 718).
33 after 35, before 48 (> 718).
46 (1st ed) after 35, without knowledge of 19 (> 718).
Second edition of 46 after 19 (> 695).
105, 110 after 40.
50 after 35 (> 718).
66 after 2, 9, 65; before 21? (?).
58, 61, 63, 98 after 9 (> 718 and more likely > 725).
This timeline was ported from my blog on 4 June 2011. It gets updated when the essays get updated. There's no need for a separate update log here.