40,000 visible polys isn't really huge. also, the more you limit your entity count, the more polys on screen you could probably have at a time (no exact equation, but i'm sure you know what i mean). four onscreen characters? i'm sure a reasonably modern computer could handle them nicely with 10,000 polys each. and if there aren't many details aside from the character onscreen EVER, then i don't see much point in putting the time into LoDs for the characters anyway. i mean, it'll be the same power-pushing for ur pc if they are all far away as it would if they are all close, which should run smoothly anyway. just check yes to mipmaps when you skin them.
this, however, is me rambling on under the assumption that physics for the characters won't be too complex, and that there won't be a lot of per-poly collisions on the actual characters. also, the more bones they have, the slower it will be. and the more animations they have. i think i'm getting carried away with my "advice". i guess you could do tests with subdivided place-holder models with big place-holder textures.
thnx for reading. i'm trying to help, but i gotta admit i'm not the most knowledgeable about this. however, from what i know, with so few characters on screen, you really have lots of room to manouver. look how high-poly characters are on DOA on the XBox. there're only two characters onscreen at a time, but the environment looks great and that's merely last-generation gaming hardware.
julz