This article introduces Innovation-Based Coaching (IBC) as a strategic framework to bridge the growing divide between AI-driven work and the predominantly content-focused nature of education. Drawing on insights from AI in education, coaching, innovation management, and employability studies, IBC uses a 3C mindset, a 3D process, and a 3M toolkit to cultivate an innovative mindset, build innovative skills, and produce innovative outputs. The 3C mindset emphasizes being Curious, Critical, and Creative; the 3D process involves Detecting, Dissecting, and Discovering to translate complex problems into targeted coaching actions; and the 3M toolkit incorporates Mapping, Measuring, and Monitoring for ongoing assessment and scaling. This approach positions AI as a collaborative partner that supports feedback, simulation, and experimentation while preserving human-centric skills such as ethical judgment, trust, and critical reflection. The article illustrates IBC in action through a case in a course, where students use AI to explore real-world issues and create tangible innovation artifacts. It also addresses major challenges, including conceptual ambiguity, cultural resistance, workload and incentive misalignments, equity concerns, and assessment difficulties, and offers practical recommendations for institutions, educators, and policymakers. The conclusion proposes a research agenda focused on IBC’s long-term impact on innovation, employability, and AI literacy, emphasizing coaching as a systemic tool to transform education in the AI era.