Or even a one time notification on OS upgrade. Perhaps with a note next to the "you should replace your battery" text in Settings.app. E.g. "this may affect phone performance, tap here for more info..."
A one time notification would be all they need. I'm an iOS developer and didn't even know that settings tells me when I need a new battery. Once told, I'd never forget.