Here's what I'm thinking, let me know if it makes sense or if there's a better way of doing it. Create a UserDefinedField of type Integer called SortField that is not visible. Then create a page handler that will take in the UserDefinedRowId and the desired action (move up or down). The page handler will first check to see if the SortField for that module is defined for each record, if it's not then it'll define it according to the order of the UserDefinedRowId in the dnn_UserDefinedRows table. So once the page handler receives the request to move a record up it'll check if it's the first record if it's not then it'll swap the SortField with the one above it. Same goes for last record.

For example given the following records listing:
0:red
1:blue
2:green

The page handler will be triggered as ".../UDTRecord.aspx?UserDefinedRowId=1&action=up"

which will give us the new listing:
0:blue
1:red
2:green

The links to move the record up or down can be generated within the XSL. Some questions though would be how to handle the display sorting and paging.  Looking forward to getting some feedback.

Frank