I've been looking at XCat and it seems like it fits may of my requirements, except a key one regarding installing it on Ubuntu or Debian OSs in general.
Does anyone have any idea or documentation on whether this is possible?
We've done little work with xCAT and debian. I know someone had made a plugin to install Ubuntu but it was never put into the main tree. You can email the list and the person who wrote it will most likely respond. Alternatively, check the archives from 2010 when it was discussed.