I can't imagine most fellowship programs (perhaps with the exception of specialties requiring minimal call -- but even so someone would need to staff the clinics) having the flexibility of a fellow starting late in August, unless the program didn't fill and they're literally just looking for someone to fill the gap (basically somebody is better than nobody at all, which is a really really low bar).
It depends on the specialty and what tier programs you're aiming for (any program vs. low tier nephro vs. top tier university nephro vs. cards/GI/heme-onc is very different), but I think the easiest way is to just take a year off and apply in your off-year to avoid this issue. Taking a year off gives you a flex year to interview without too many schedule constraints and also lets you make money as an attending on the side, which isn't bad at all. That said, many programs will ask you why you are taking a year off, in which case you will have to explain why you had to graduate late, but that's better IMO than going in and saying you need to start fellowship late because of whatever issue (basically, you'll have to bring it up anyway so might as well make it less of a hindrance for the programs to rank you).