Features and Patterns for Managing Ordered Lists
The last is a technique used quite often, and that works. If you're afraid of running out of decimals you can refine it to detect when the average between the next two previous/following values cannot be distinguished from one of them (i.e.: you run out of decimals). 

When this happens, you should resequence as many rows up or down as needed. 

Let's assume you work with just 2 decimals, and you have two rows with Seq 1.00 and 1.01; the next value being 2.00. If you want to move a row using your technique between these two, you would have Seq = (1.00, 1.005, 1.01, 2.00). This would need more decimals than are available and, depending on the rounding rules, 1.005 would either be rounded to 1.00 or 1.01. In any case, you can detect that the inserted value is not distinguishable from either 1.00 or 1.01. 

In that case, you need to "push down (or up) and make room". That is, you should change one more row, and have (1.00, 1.25, 1.50, 2.00). You've spread the change to two rows instead of just one. 

This might need to be done recursively (or iteratively) if you ever run into a situation such as (1.01, 1.02, 1.03, 1.04, ...).

With this extensions to your original technique, you don't need to renormalize. This is taken care of only in an "as needed" basis, and scales quite well.

NOTEs: 


Implementing the algorithm might be a bit tricky, because you need to take into account when you're at the first or last rows, and how to handle those, and when your Seq numbers reach the maximum or minimum available values. 
The algorithm works with any number of decimals, including 0. That is, you can use it as well with integer values instead of decimal, which might prove more computing efficient, or, depending on how decimals are implemented, be also more space efficient.