Ale co dokładniej będzie to robić? Bo z tego co wyczytałem geofencing może być wykorzystany na różne sposoby do różnych celów.
1. W Shared Preferences raczej zapisuje się mało danych, jakieś ustawienia, wybrany język, może lokalizacja ostatniego zalogowania, ale jeśli chcesz zapisać więcej danych typu właśnie jakichś wielu lokalizacji to lepiej w SQLite albo w jakimś swoim pliku.
2. Możesz to zrobić z pomocą klasy Service. To jest PRZYKŁAD a tu TUTORIAL dotyczący klasy Service.
3. Musisz poczytać dokumentację klasy Service w szczególności zwróciłbym uwagę na parametr android:process w Manifeście.
4. A skąd te ograniczenie? Powiedz więcej na czym polega aplikacja, i czy korzystasz z jakichś dodatkowych API?