How to _really_ programmatically change primary and accent color in Android Lollipop?

Themes are immutable, you can't.

I read the comments about contacts app and how it use a theme for each contact.

Probably, contacts app has some predefine themes (for each material primary color from here: http://www.google.com/design/spec/style/color.html).

You can apply a theme before a the setContentView method inside onCreate method.

Then the contacts app can apply a theme randomly to each user.

This method is:

setTheme(R.style.MyRandomTheme);

But this method has a problem, for example it can change the toolbar color, the scroll effect color, the ripple color, etc, but it cant change the status bar color and the navigation bar color (if you want to change it too).

Then for solve this problem, you can use the method before and:

if (Build.VERSION.SDK_INT >= 21) {
        getWindow().setNavigationBarColor(getResources().getColor(R.color.md_red_500));
        getWindow().setStatusBarColor(getResources().getColor(R.color.md_red_700));
    }

This two method change the navigation and status bar color. Remember, if you set your navigation bar translucent, you can't change its color.

This should be the final code:

@Override
protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setTheme(R.style.MyRandomTheme);
    if (Build.VERSION.SDK_INT >= 21) {
        getWindow().setNavigationBarColor(getResources().getColor(R.color.myrandomcolor1));
        getWindow().setStatusBarColor(getResources().getColor(R.color.myrandomcolor2));
    }
    setContentView(R.layout.activity_main);

}

You can use a switch and generate random number to use random themes, or, like in contacts app, each contact probably has a predefine number associated.

A sample of theme:

<style name="MyRandomTheme" parent="Theme.AppCompat.NoActionBar">
    <!-- Customize your theme here. -->
    <item name="colorPrimary">@color/myrandomcolor1</item>
    <item name="colorPrimaryDark">@color/myrandomcolor2</item>
    <item name="android:navigationBarColor">@color/myrandomcolor1</item>
</style>

Sorry for my english.

You can use Theme.applyStyle to modify your theme at runtime by applying another style to it.

Let's say you have these style definitions:

<style name="DefaultTheme" parent="Theme.AppCompat.Light">
    <item name="colorPrimary">@color/md_lime_500</item>
    <item name="colorPrimaryDark">@color/md_lime_700</item>
    <item name="colorAccent">@color/md_amber_A400</item>
</style>

<style name="OverlayPrimaryColorRed">
    <item name="colorPrimary">@color/md_red_500</item>
    <item name="colorPrimaryDark">@color/md_red_700</item>
</style>

<style name="OverlayPrimaryColorGreen">
    <item name="colorPrimary">@color/md_green_500</item>
    <item name="colorPrimaryDark">@color/md_green_700</item>
</style>

<style name="OverlayPrimaryColorBlue">
    <item name="colorPrimary">@color/md_blue_500</item>
    <item name="colorPrimaryDark">@color/md_blue_700</item>
</style>

Now you can patch your theme at runtime like so:

getTheme().applyStyle(R.style.OverlayPrimaryColorGreen, true);

The method applyStylehas to be called before the layout gets inflated! So unless you load the view manually you should apply styles to the theme before calling setContentView in your activity.

Of course this cannot be used to specify an arbitrary color, i.e. one out of 16 million (256³) colors. But if you write a small program that generates the style definitions and the Java code for you then something like one out of 512 (8³) should be possible.

What makes this interesting is that you can use different style overlays for different aspects of your theme. Just add a few overlay definitions for colorAccent for example. Now you can combine different values for primary color and accent color almost arbitrarily.

You should make sure that your overlay theme definitions don't accidentally inherit a bunch of style definitions from a parent style definition. For example a style called AppTheme.OverlayRed implicitly inherits all styles defined in AppTheme and all these definitions will also be applied when you patch the master theme. So either avoid dots in the overlay theme names or use something like Overlay.Red and define Overlay as an empty style.