I hate it when companies think that they can get away with making you pay for your data.
From looking around the FitBit site, it seems they are in California, so Californian law applies. No EU Data Protection Directive there I'm afraid. (If they were in EU their terms & conditions would probably not be binding anyway, against the EU Unfair Terms & Conditions Directive)
Individuals must have access to personal information about them that an organization holds and be able to correct, amend, or delete that information where it is inaccurate, except where the burden or expense of providing access would be disproportionate to the risks to the individual's privacy in the case in question, or where the rights of persons other than the individual would be violated
It would be interesting to send them a request and see what their position is.
From my understanding, from the yearly IG briefings I used to have, you would be able to provide that requester with information on how to obtain their personal access, and point out to them where they can find the information they have requested.
Information needs to be made accessible, you don't necessarily need to actually provide printouts. For example, FOI requests from news agencies often cover the same topics. This information can and often is posted publicly on the organisation's website and the FOI responses refer the requester to those links.
What if the FOI request was supplemented with the users password (changed by them to a temporary one)?
Other possibilities would be encrypting a second copy of the patients data (each time it is stored by the user) using a public key with the corresponding private key held in escrow somewhere on a machine with no network connection. It would then be someone's job, upon receiving an FOI request, to take the patients master-encrypted record(s), put them on the non-connected computer that contains the private key, decrypt, and print out in order to reply to the FOI and then clean up.
You must track each and every time a patient's data was decrypted and by whom, and that information must be available as well.
Information that you'll probably also need to encrypt, but still be able to search by patient, date, and decrypter. (requests come through to find all records a particular employee has seen within a certain date range as well)
I can see the start of a rabbit hole, which is why organisations dealing in PID have IG teams or consultants who know the laws and know how much needs to be done.
If a patient thinks an organisation is holding out on them, that patient has a way to complain, and the complaints aren't taken lightly from what I've seen.
What would be ideal is to have some kind of "password/data escrow" service that is separate from companies like yours, or the one I'm working with, so that there is a way to recover the data if a password is lost, but a formal/legal separation of the means to access it is maintained.
Minor pedantic peeve of mine: Many countries have Freedom of Information (FOI) laws, and Data Protection. Often FOI only refers to government bodies and covers lots of stuff (e.g. "How much per year does my local council spend cleaning the local park?"), however data protection mostly applies to personal data that anyone (government or private enterprise) holds on you. Data Protection laws sometimes make it illegal for the company to tell third parties the personal data about you.