Applying the Decorate-Sort-Undecorate idiom using any version of the mandatory POSIX tools awk, sort, and cut:
$ awk -v OFS='\t' '{print (NR>2), $0}' file | sort -k1,1n -k2 | cut -f2-
:0:12345
:1:6:2:3:3:8:4:2
010005TSTDOG_FOOD01
222334NOTALINEOUT01
325611LVEANOTHERS00
477821USASHUTTLES21
500123TSTMY_RADAR00
Works just fine on incoming piped input too:
$ cat file | awk -v OFS='\t' '{print (NR>2), $0}' | sort -k1,1n -k2 | cut -f2-
:0:12345
:1:6:2:3:3:8:4:2
010005TSTDOG_FOOD01
222334NOTALINEOUT01
325611LVEANOTHERS00
477821USASHUTTLES21
500123TSTMY_RADAR00