To me, uninstalling all Social Media did wonders on my productivity. I replaced them with instapaper (for articles I saved before hand) and Kindle. Now, I can't mindlessly loose track of time on twitter or something, and if I am truly using my phone to fill some in-between time waiting for a doctors appointment or something, I am doing something I already previously decided to do, not something I come up with (an article/book I already picked out), so I am no susceptible to temptation.

One thing I would add to this, is either disable, or put in the same folder as the other distracting apps, the web browser. You really need it for a surprisingly little things on your phone, and I found it as an alternate route to my time wasting websites.