Mobile phones are low power, rugged, cheap, and well accepted in Zambia. I think I'd be looking at how much of the electronic medical record keeping I could push onto very basic mobile phone-based services such as SMS, MMS, voice/voice recording, and/or (for example) very lightweight Java ME applications (using MQTT probably which is free, bidirectional, low power, secure, and extremely bandwidth efficient/tolerant). Voice input, for example, is very fast -- faster than writing/typing at the point of service -- and labor is cheap to take dictation locally or remotely. A cheap camera phone can take decent pictures of body parts and what they look like. Patients with mobile phones -- many of them -- can input their own histories for registration (via a Java ME or WAP app probably), or somebody remote can call them who can then key in the history via Q&A -- even before they get to the clinic. Get an IBM "Watson" (or connect to one in the "cloud") for diagnoses. And so on. Think of how to deliver as many and as much of the business processes via mobile feature phones and (for the clinics) slightly more advanced tablets with very lightweight protocols and near-ubiquitous services. I agree with the commenters upthread: stay away from the paper if at all possible. If there is any paper, let them use the manual typewriters they already might have and then have a "scanning station" with a camera phone on a tripod sort of thing to get the paper "into the system" immediately.
As for freezer labeling, how about not labeling at all in the field? Get tubes/containers pre-marked "at the factory" with unique sequential barcodes and serial numbers, and then associate that tube with the patient electronically when the sample is collected. The technician would also jot down the patient's assigned code using a simple freezer-compatible pen/marker. Again, a simple mobile phone with a camera would be able to scan the barcode on the tube and look up the patient code (or register the patient to that tube). The code could be something as simple as the patient's mobile phone number concatenated with a couple alphanumerics: initials, date of birth, or something else. (This would depend on the cultural context of course. It should be short, unique, avoid characters that can be mixed up like 0 and O, and have a check character embedded to avoid false match errors.)
Get hold of portable property. -- Charles Dickens, "Great Expectations"