Storing the old value for future use...lol. I still ended up needing to check if the old_value was None. You have to re-define your do_stuff function in order to truly get rid of the if statement. This of course uses more memory than just checking every time. Possibly as much as perhaps 15 machine words, or more...gasp!

RecallMyProperty.py

from kivy.event import EventDispatcher
from kivy.properties import NumericProperty

class Eoo(EventDispatcher):
    new_value = NumericProperty()

    def __init__(self, **kwargs):
        self.old_value = None
        super(Eoo, self).__init__(**kwargs)
        self.bind(new_value=self.recall)

    def recall(self, instance, value):
        self.old_value = value
        def new_recall(instance, value):
            # do something with the old value
            # doing stuff....
            self.do_my_thing(self.old_value, value)
            # after you're done, store the next old_value
            self.old_value = value
        self.unbind(new_value=self.recall)
        self.recall = new_recall
        self.bind(new_value=self.recall)
        self.do_my_thing(None, value)
        
    def do_my_thing(self, old, new):
        if old is not None:
            print 'I used to be: ' + str(old)
        print 'But now I\'m: ' + str(new) + '\n'

e = Eoo()

e.new_value = 1
e.new_value = 2
e.new_value = 3