It's definitely possible. I am currently a pulm-crit fellow after serving a 4 year obliation and I know of several others. My advice would be to complete a research
project as a resident and meet with faculty who will write letters for you prior to finishing residency. When you actually apply for fellowship, I would again get in touch with those faculty and update them on what you have been doing after residency.
If you plan on doing a fellowship with a significant inpatient component, it would make most sense to work at a NHSC site where you are still doing a significant amount
of inpatient work (most likely rural or IHS sites)..