Is it possible to change my username on YouTube? If not, is there a way to move my videos from one account to another new one? (An automated way, rather than downloading them then uploading them to the new account.)
No, you cannot change your username—there is a lot of user information linked to the account that will need to be broken. You will need to create a new account.
See Google's Youtube Support for more information.