What's the decoding time complexity of LT codes?
The approach you describe can be implemented to run in linear time.

Build a bipartite graph where left-vertices are blocks and right-vertices are packets, and with an edge from block $b$ to packet $p$ if $b$ is one of the blocks xor-ed to create $p$'s message.  Store the bipartite graph in adjacency list format.  Also keep track of the degree of each packet, so given a packet $p$ you can compute its degree in $O(1)$ time.

Then it's easy to implement the algorithm you describe in $O(n)$ time, using a worklist algorithm.  The worklist is a list of all packets of degree one.  In each iteration, you remove a degree-one packet $p$ from the worklist, then process it as follows.  Find the corresponding block $b$, then find all other packets $p'$ containing the block.  Xor $b$ into $p'$, and delete the edge $(b,p')$ (and update the degree of $p'$).  This can be done in $O(1)$ time.  If the new degree of $p'$ is 1, add $p'$ to the worklist.  Repeat until the worklist is empty.

The running time is $O(1)$ per edge in the bipartite graph, i.e., $O(m)$ time where $m$ counts the number of edges in the graph (the sum of degrees of all of the packets).