An alternative is that you pay for yourself to move out there prior to the job hunt. :)
Employees are replaceable; so are jobs. The important thing is to remember where you are in the process.
Take a look at what you wrote: it sounded like the perfect opportunity, I felt this position was perfect for me. Remember that they person on the other end of the phone is not interested in if the position is perfect for you-- he's interested in if you are perfect for the position.
If I were you, I'd make sure that I was sending out a vibe of "this is how I can solve your problems", not "what can you do for me?" If you can convince them you are the best guy for the job, getting the relocation paid won't be a problem-- trust me. I've hired employees from far-off countries, at great expense and hassle with visas, because I felt they were the right person to do the job.