One approach would be to weight each timestamp with the time since the previous timestamp. In other words, sort the timestamps in increasing order and then let the timestamps be $t_1,t_2,\dots$. Now, weight the timestamp $t_i$ with weight proportional to $t_i-t_{i-1}$. Finally, sample from the timestamps, choosing each possible timestamp with a probability proportional to its weight. This will ensure that the selected timestamps are distributed uniformly across time.
You can also look at variants of this, where you do some kind of smoothing. For instance, given a timestamp $t_i$, you can look at the 5 previous timestamps, compute the average duration between them, and choose a weight based on that; this amounts to choosing $t_i$ with probability proportional to $t_i - t_{i-5}$. Or, you can choose a fixed duration $d$, and choose a timestamp $t_i$ with probability that is proportional to the number of events that occur in the window $(t_i-d,t_i]$ (i.e., proportional to $|\{j : t_i-d < t_j \le t_i\}|$). The latter is similar to your histogramming idea, so might be a bad choice -- the problem is that you have to choose a fixed duration $d$, which might be problematic. So try my other suggestions.
There's no way in general to choose a sample that is simultaneously uniform in both dimensions. For instance, suppose your timestamps are evenly spaced through time, where the earliest 80% have phase 0 and the latest 20% have phase 1; then there's no distribution on timestamps that is simultaneously uniformly distributed in time and uniformly distributed in phase.
However, you can choose one sample that is uniform in one dimension, and uniform in another dimension.
