Make a smart card (and associated readers) that allow the person to choose and approve exactly what information is given. This keeps control of the data in the hands of the individual instead of keeping it in some centralized database that you can't control.
Give each person a smart card that stores
the person's health information. The data on the card would be protected (encrypted) and would require the person's approval to access it. The information could be catogorized to make it easy to get to related information. There could also be a setting to allow extra access to emergency personnel (the info that can be accessed is determined by the person). Ideally some of the user interface would be built into the card but it may have to be built into "approved" readers. Health businesses would buy readers that connect to their computers. Their computer sends a request to the card reader asking for specific pieces of information. You put your card into the reader and it tells you what was requested, asks for your approval, and ask for your password (or passwords) to allow access to that information. You could approval the transfer of all of that information or just parts of it. If any information was approved the reader would send it back to the computer and spit your card back out. Besides medical this could be used anytime someone else needs information about you.
Dentist: You go to the dentist and they ask for your name, address, and current medications and you approve name and address. They don't get anything else.
Doctor: You go to the doctor and they request your whole medical history and you approve it.
Store: You go to a store and decide to sign up for a contest. They ask for your name, address, and telephone but you approve only name and address.
Theme park: You go to a theme park that charges different fees based on age. They request just your age and that is all you approve.
Emergency: You are in a car accident and are unconscience. An EMS arrives, puts your card in a reader, and receives exactly the information that you already choosen that emergency personel should be able to see. (Ignore how emergency personnel are identified for now.)