On this page of the game guide to Borderlands 2 you will find a detailed description of the side mission titled Rock, Paper, Genocide. This is one of the few side missions that you can begin during your first visit to the Sanctuary.
You can receive this mission during your first visit to Sanctuary.
1) Marcus' shop
Go down the stairs to Marcus' shop . Speak to him and head to the shooting range at the back of the shop through the door on the right. Use the Fire Elemental Effect weapon on the Bandit. Afterwards speak with Marcus to get another task, this time with the use of a weapon with Shock Elemental Effect. You can find one I your inventory. Turn in the mission to get another one.
Now you will have to shoot a Robot with a Corrosive Elemental Effects weapon. Finally, you will need to use a Slag weapon followed by any other with an Elemental Effect.