Johann,
the steps as i see it:
- add new uuid field for your new primary key, don't drop old one yet
- fill in the uuid field
- add a new foreign key field that will store UUID
- use the old foreign key to lookup the uuid of the reference
- store that uuid
- alter tables to make the uuid fields the primary and foreign keys from the database's perspective
- drop the old id columns
you'll have to do that with some sql scripting, and then update your web2py model files accordingly.
good luck!
christian