Black wire crossed with white in box
You don't need to put in another box somewhere, but if you want the lights controlled separately and the outlet always on, you will need to run another cable from the switch box to the outlet box. 

The new cable does not have to physically follow the existing cable, it just has to connect the same two junction boxes. 

You can't just add a /2 cable and use both wires as switched hots with return via the neutral wire in the existing cable. Electrical codes and safety considerations require that all current that flows through a hot wire to a load must return via a neutral wire in the same cable. 

You can either abandon or remove the existing /2 cable and replace it with a /4 cable, or keep the /2 and add a /3 cable. 

If you install a /4 cable, the wiring is simple. You have one neutral, a constant hot, and two switched hots. Three loads use one hot each, and they all share the one neutral. 

If you add a /3 cable then it is vital that you keep the two cables completely independent, so that one of the three loads is connected only to the hot and neutral in the /2 cable, and the other two loads are connected to the two hots and the one neutral in the new /3 cable.