You've asked two questions in your post:
For the order of application: Character creation is broken into steps for ease of creation, not out of necessity. Whether you start with the background, race, or class is irrelevant since the process is a whole not a stepping program.
The only exception to this was the one I left out, which is attribute roles. I assume standard array when dealing with questions unless OP states otherwise, however I'll address that in the event your group is playing with a more hardcore mindset and has you roll attributes after the character has been built, you may end up with a rather weak Barbarian, incredibly irritating Bard (so a Bard), or a stupid Wizard. Of course, you could end up with an extremely dexterous warlock or a very durable sorcerer!
The point here is that if your group has different rules in play than the PHB does, it will significantly alter the answer. As per RAW, the order is entirely irrelevant.
For the skill proficiencies: You can do whatever you want for each proficiency of your background.
Your answer is on PHB. pg. 126, emphasis mine:
Customizing a Background
You might want to tweak some of the features of a
background so it better fits your character
or the campaign setting. To customize
a background, you can replace one feature
with any other one, choose any two
skills, and choose a total of two tool
proficiencies or languages from the
sample backgrounds. You can either use
the equipment package from your
background or spend coin on gear as
described in chapter 5. (If you spend
coin, you can’t also take the equipment
package suggested for your class.)
Finally, choose two personality
traits, one ideal, one bond, and one flaw. If you can’t find
a feature that matches your desired background, work
with your DM to create one.