My partner and I just biked through the keys to finish a multi month trip. John Pennekamp Coral Reef State Park, Curry Hammock State Park and Bahia Honda State Park all make special accommodations for through bikers/hikers/paddlers. We only stayed at both Curry Hammock and Bahia Honda as we basically had an off-day to burn. They're only 18 miles apart and given the choice, Curry Hammock would be a very easy pick for me. We took the ferry from Key West to Fort Myers same day we arrived, so we didn't actually stay in Key West.
John Pennekamp (Key Largo) seemed to have the least planned policy and told us over the phone that they usually try to figure something out for through bikers, but it may depend on the specific park ranger that we speak to. We ended up staying with some wonderful warm showers hosts instead.
Curry Hammock (Marathon) has a spot right on the beach where they put us. I'm not sure if that's the arrangement they always make though. It looked like it may be a group camping site as they did have to double check availability when we called (maybe 3 days in advance). It was beautiful, quiet, had very little light pollution and was not particularly buggy. It was probably our favorite camping spot of the entire trip (we camped maybe 1/3 of the time).
Bahia Honda (Big Pine Key) reserves site #80 for through bikers/hikers/campers up until I think 2 pm after which it's available to anyone. We called a few days in advance to reserve it. It's also right by the water (the last in their row of primitive sites), but in a somewhat swampier area and the no-see-ums bites were pretty brutal. It was also pretty close to the highway so you could still hear cars going by all night.