Вы можете добавить android: required = "false" флаг к вашему файлу манифеста, и приложение должно иметь возможность запуска.
<uses-library
android:name="com.google.android.maps"
android:required="false"/>
Тогда вы должны быть уверены, что защитите свой код от исключения в тех местах, где оно вам нужно. Вы можете попробовать что-то вроде этого, чтобы проверить наличие библиотеки:
Class.forName("com.google.android.maps");