There is no way to add permissions at runtime, they must be explicit in the AndroidManifest because they need to be presented at installation to the Android User.
May I suggest you take a look at the following post: Permission issue while starting a service from android
Global access to a service can be enforced when it is declared in its
  manifest's tag. By doing so, other applications will need to declare a
  corresponding element in their own manifest to be able to start, stop,
  or bind to the service.
As of GINGERBREAD, when using Context.startService(Intent), you can
  also set Intent.FLAG_GRANT_READ_URI_PERMISSION and/or
  Intent.FLAG_GRANT_WRITE_URI_PERMISSION on the Intent. This will grant
  the Service temporary access to the specific URIs in the Intent.
  Access will remain until the Service has called stopSelf(int) for that
  start command or a later one, or until the Service has been completely
  stopped. This works for granting access to the other apps that have
  not requested the permission protecting the Service, or even when the
  Service is not exported at all.
In addition, a service can protect individual IPC calls into it with
  permissions, by calling the checkCallingPermission(String) method
  before executing the implementation of that call.
See the Security and Permissions document for more information on
  permissions and security in general.