Hi Martin
If I am not mistaken, this is equivalent to (or a part of) Zero Configuration Networking based on the use of "Dynamic Configuration of IPv4 Link-Local Addresses". It is also related to IPV6's "Stateless Address Autoconfiguration".
In the case of IPV4, after reading the first half of the RFC, it seems fairly simple to allocate random link-local addresses and test and defend them according to the specification - DHCP does some similar testing for address collisions. To do it properly there are a number of things in the specification that need to be considered more, such as handling collision detection, giving up addresses, timeouts after various events are detected, and such.
The other question is how to best transition between the use of a routable address and the link-local address. The two shouldn't generally be used at the same time but during transition phases it does look as though it is possible.
Therefore I would estimate that assigning and using a link-local address would not be complicated. A larger amount of work would be required to handle all of the requirement according to the RFC in all circumstances, with some experience gathering in real application cases, whereby transition between the two modes, and especially phases where both could be in operation at the same time, could be a little trickier.
Regards
Mark