My wonderful colleague created this script in Python for me. It does exactly what I have described above.
I have attached it.


import maya.cmds as mc
import os

def rename_lod(path, name, n):
if "LOD" in name:
name = name[:-5]
print "Renaming", path, "to", name
rels = mc.listRelatives(path, children=True, fullPath=True)
print rels
if len(rels) == 1:
mc.rename(path, name+'_LOD'+str(n))
return
elif len(rels) > 2:
print "Too many children in one layer"
os.exit(1)
else:
child = rels[1]
rename_lod(child, name, n+1)

mc.rename(path, name+'_LOD'+str(n))


sel=mc.ls(selection=True)

for each in sel:
try:
name = each.split('|')[1]
except:
name = each
rename_lod(each, name, 0)