European cities are increasingly exploring artificial intelligence (AI) applications to achieve their climate goals. Yet, how European city administrations implement AI-for-climate projects remains unclear. To address this gap, we interviewed city staff and urban innovation experts (n=15 interviewees) from Amsterdam, Berlin, Copenhagen, Greater Paris, Helsinki, and Vienna about their motivations, challenges, solutions, and partnerships when deploying AI tools. We found that city administrations were driven by different priorities that extend beyond accelerating climate action, such as improving decision-making, providing better services to residents, reducing costs, and showcasing innovation. We also identified implementation challenges for city administrations, for instance, socio-technical interoperability with existing systems or increasing AI literacy among city staff who work on climate action. We characterized three implementation arrangements through which cities deployed AI, highlighting the plural roles of city administrations in shaping AI deployment. Our analysis indicates that the European Commission, start-ups, researchers, and innovation labs were key partners for implementation, unlike civil society and large technology firms. Our study also reveals substantial challenges even for large, affluent cities, creating doubt about the applicability of AI projects for climate change mitigation in small and medium-sized cities.