> >At first, I think that I will need their certificate to sign the app, isn't?
Have them add you as a team member, so you can log in and do the upload for them. Then, on whoever's machine is their primary account contact, export a P12 certificate from their Keychain Access, and import that file into your Keychain Access. After that you should be able to log in to their account and create the distribution provisioning files, do the build, and upload to their account (assuming they gave you the right level of access).
The upload process involves a lot of questions, so when I did that with an app I had screen sharing on, and my client was watching, and sending over Word files with all the description texts already laid out. I just had to copy and paste things into the right slots.