@Doctrg You should be able to go straight from 1.3.5 to 1.5.4 I think. Make a full DB dump on the old server, install mysql on the new one by hand (yum install mysql mysql-server), import DB dump and then start the FOG 1.5.4 installer. When it asks you to open the web interface go ahead and it should upgrade your database structure - usually does without an issue.
Not saying there can’t be anything going wrong but mostly this is going fine. As you still have the old server (or at least a full backup of machine and DB), you can always give it a try. Shouldn’t hurt.