There are two separate issues here:
1. Transferring data plans
This is best dealt with directly through your carrier as CajunLuke notes. For person A, a simple SIM swap should work though, for person B you'll need to cut the 3G's SIM down to micro-SIM size to fit in the iPhone 4. And you can probably swap the SIM from the dumbphone into the 3G and have the appropriate data plans added on the account. Still check with your carrier to avoid headaches.
2. Transferring backups amongst the iPhones
This is pretty straightforward. It sounds like the iPhone users have already got them backed up, so you're most of the way there. Do a final backup, and make sure they remember the passwords.
I'd start with the 4S, since it's a clean phone anyway. When you plug it in to iTunes and activate it, it should ask if you want to set it up as a new iPhone, or restore it from a backup. If it doesn't, just right-click the iPhone in the iTunes source list and choose Restore from Backup. Check to make sure everything seems right on the phone, then you're good to go.
To set up the iPhone 4, start by wiping it clean (this is why you want to do the 4S first, in case something goes wrong, you still have the data on the 4). Go to Settings > General > Reset and select Erase all Content and Settings. You'll have to enter the phone's passcode if you use one. Once the wipe is complete, plug it in to Person B's computer and set it up via iTunes as you did with the 4S, but using the backup from Person B's 3G.
To set up the 3G, repeat the wipe process above, but set it up as a new phone in iTunes for person C. If the dumbphone has Bluetooth sync capability, you can try transferring contacts to the PC that way using iSync and Address Book (note that Lion no longer includes iSync, you'll need a 10.6 machine or lower). Alternatively, if the phone stores the contacts on the SIM, or has the option to copy them there, you can import SIM contacts on the iPhone by going to Mail, Contacts, Calendars in Settings and selecting Import SIM Contacts.
Apple has a good KB article detailing any additional information you might want located here.
You can set up multiple different iCloud accounts in the "Mail, Contacts, and Calendars" preference panel, and also on your iPhone and iPads.
I have accomplished a shared address book with my partner by each of us having a primary iCloud account (me@us.com, her@us.com) - and then a shared iCould account us@us.com.
One annoying downside is that the Lion Address Book app labels both address books as "iCloud" making it a bit hard to distinguish what contacts are where. We solve this by having different contact lists in each address book, so they are distinct.
It seems with just a little bit of work Apple could make this MUCH better, but this is the best solution I have seen so far.
Best Answer
Assuming your talking about Windows and the other user has administrator rights:
There are tools that may allow the Windows administrator account (which has access to all files on the computer) to view locally stored backups and extract them. This will only be possible if the data is actually on this computer, and not encrypted.
If you are sure that is not the case –because you only backup to iCloud– this person will need your Apple ID and password to access your iCloud data. This information may be stored in your session (recorded by Chrome for instance) but it is encrypted with a key associated with your Windows password, so not accessible to the administrator.
If the administrator changed or knew your Windows user password he could have accessed your session and pretty much all of your data. You will notice on the first case because he will have asked you to recreate it, or use a new one. It does not seem possible for the administrator to see your stored password, only to reset it.
Finally, someone could have installed a keylogger or some other form of monitoring on this computer, and all the information entered could be retrieved.
On the other hand iMessage is encrypted end to end according to Apple and others, but probably available to Apple or someone with access to Apple's servers (see this answer on Information Security SE). Sniffing your traffic on the local network and extracting iMessage from there does not seem to be a feasible attack vector.
To keep this from happening:
If you use the PC to access iCloud