This is my first thought of how to implement this:

package List::ResetOnTheHour;

sub new {
    my $class = shift;
    my $self  = {
        list           => [@_],
        embargo_1_hour => [],
        embargo_2_hour => [],
        last_check     => 0,
    };
    return bless $self, $class;
}

sub next {
    my $self = shift;

    my $list = $self->{list};

    # compare last_check against time and push embargo_1_hour back
    # onto list if the top of the hour has passed. push embargo_2_hour
    # onto embargo_1_hour or list depending upon how much time has
    # passed.

    my $next = splice @$list, -1 + int rand @$list, 1;

    # if within 5 minutes of next top of hour, push onto
    #     embargo_2_hour,
    # else push onto embargo_1_hour

    return $next;
}

# This would be used instead of the constructor to add items when a
# last used time is already known, like when reading from a
# serialized state file on startup.
sub add {
    my ($self, $elem, $time) = @_;
    # add to list or embargo_X_hour depending on value of time.
}
[download]