The Increment Selection package might be what you're looking for. It seems to be working with multiple cursors, so should be pretty close to your use case:
Select a block of text and hit ctrl-shift-i to replace it with incrementing numbers
- Uses first line's number if any
- Works with multiple cursors