Another suggestion was given on StackExchange: use IncidenceMatrix and derive the edge list for the positions and values in the (sparse) incidence matrix. I used a LibraryLink function to do this fast. This solution is now used by IGraph/M 0.3.95, and also exposed by it as the IGIndexEdgeList function. This function is even faster than EdgeList, especially for large graphs, thus it is useful for implementing fast edge-list based operations.

The following won't work for multigraphs, but it is faster for the other graphs:

elist[g_Graph] := With[
    {sa = UpperTriangularize @ WeightedAdjacencyMatrix[g, EdgeWeight->Range@EdgeCount@g]},

    sa["NonzeroPositions"][[InversePermutation @ sa["NonzeroValues"]]]
]

Check:

Grid @ Table[
    With[
       {
       r1=AbsoluteTiming[Flatten[elist[Symbol@g]]-1],
       r2=AbsoluteTiming[igEdgeList[Symbol@g]]
       },
       {g,r1[[1]], r2[[1]], r1[[2]]===r2[[2]]}
    ],
    {g, {"g1","g2","g3","g4","wg1","wg2","h1","h2","h3","h4","wh1","wh2"}}
]

g1  0.052843 0.276878    True
g2  0.051412 0.283879    True
g3  0.048165 0.222559    True
g4  0.050206 0.239958    True
wg1 0.049296    0.228189   True
wg2 0.048674    0.263723   True
h1  0.081907 0.11832     True
h2  0.084709 0.241035    False
h3  0.077764 0.124032    True
h4  0.082046 0.21298     True
wh1 0.080524    0.118146   True
wh2 0.077027    0.232665   False

The two discrepancies occur because some of the edges are reversed. For example:

Sort/@elist[h2] - 1 === Sort /@ Partition[igEdgeList[h2],2]
Sort/@elist[wh2] - 1 === Sort /@ Partition[igEdgeList[wh2],2]

(* True *)

(* True *)