Do I need to SSH into EC2 instance in order to start custom script with arguments, or there are some service that I don't know
You can use knife-bootstrap. This can be one way to do it. You can use AWS SDK to do most of it

Launch an instance
Add a public IP (if its not in VPC)
Wait for instance to come back online 
use knife bootstrap to supply script, setup chef-client, update system
Then use chef cookbook to setup your machine
I need to create an application that will do the following:

Accept request via messaging system ( Done )
Process request and determine what script and what type of instance is required for the job ( Done )
Launch an EC2 instance 
Upload custom script's (probably from github or may be S3 bucket)
Launch a script with a given argument.

The question is what is the most efficient way to do steps 3,4,5? Don't understand me wrong, right now I'm doing the same thing with script that does all of this 

launch instance, 
use user_data to download necessary dependencies
than SSH into instance and launch a script

My question is really: is that the only option how to handle this type of work? or may be there is an easy way to do this?
I was looking at OpsWork, and I'm not sure if this is the right thing for me. I know I can do steps 3 and 4 with it, but how about the rest? :

Launch a script with a given argument
Triger an OpsWork to launch an instance when request is came in

By the way I'm using Python, boto to communicate with AWS services.