How important is the choice of the initial state?
The initial state can vary during in both training and use, and how you decide to do this makes very little difference to Q-learning. The important factor is whether all state/action pairs relevant to optimal behaviour can be reached. As there is already randomness in any exploring policy, and in many environments as part of state transitions and reward functions, adding some more at the start is not an issue.

More formally, you can take any existing environment with states $S_1, S_2, S_3 ... S_n$ plus defined actions and rewards. Add a special fixed start state $S_{0}$ with one special action $A_{0}$ allowed. Make the state transition matrix following that action any distribution you like over the other states, and reward $0$. It is clearly a valid MDP, and is identical to your original MDP in terms of value and policy functions for states $S_1, S_2, S_3 ... S_n$. For all intents and purposes to the agent (which gets no meaningful policy choice in $S_0$), it starts in the original MDP in some randomly chosen state.

That is as long as the variations are not made to deliberately exclude some of the state space during training that it would need later, or otherwise used to "attack" the agent and prevent it learning. Q-learning proofs of convergence assume that all state/action pairs are reachable an infinite number of times in the limit of infinite training time. Of course in practice this is never achieved, but clearly if you excluded some important state from ever being seen at the start by choosing to start in a way that it is never reachable, then the agent would never learn about it.

You can use a highly variable start state for training to your advantage. It is a form of exploration, and truly exploring starts (that could start from any state/action pair, so you would want to randomise the first action choice) allow you to skip any further exploration and still guarantee convergence to an optimal policy - i.e. you could learn Q values on-policy using a deterministic policy. This will not necessarily make things converge faster, but does go to demonstrate that random start states are not a barrier to RL.

There are a couple of minor/partial exceptions to "do what you like":


If the environment is otherwise highly deterministic, adding a random start may increase the difficulty in optimising it, as more states will be reachable, even with an optimal policy, therefore the state space over which optimal behaviour needs to be discovered may be larger and take longer to learn.
Policy Gradient methods, like REINFORCE, optimise the policy towards maximising return from a known distribution of start states. So you can vary start state, but you should really stick to a standard start procedure, including a fixed distribution of allowed start states. 
Similarly, if you want to report a standard score for your agent, it is common to quote the expected return from the start states. Again that doesn't mean you have a fixed start state, but you should use a fixed distribution of start states to assess your agent.


Many standard environments, like Open AI's Gym environments CartPole and LunarLander, include some amount of randomness in the start state, so that the agent has to solve a more general problem than just generating a fixed sequence of actions that always works from the beginning.