Creating partner portal is free. Please correct me if I am wrong. I want to start security review for a free application from my AppExchange profile but I can't do that before paying to salesforce. Is that correct?
Looks like techtrekker has the right answer for you. But actually, I wouldn't rely on just the opinions or experiences of people here for this question. Why? Because I've been through the process many times (all for paid apps that I've developed) and my first thought when reading your post was that free apps are free to get certified and listed. I believe that was the case at one time from something I read. Perhaps, but it's most likely incorrect now.
Sounds like $300 is the deal but again, you need to confirm this with Salesforce. I'd log a case in your portal with this question. You should get a response within 48 hours.
I haven't personally been through this process, but I've read some, here are some excerpts which may help answer your question.
Step 2 at http://wiki.developerforce.com/page/Security_Review states :
2. Initiate Security Review - Initiate security review of your offering by logging into the AppExchange Publisher Profile (www.appexchange.com) and clicking "Start Review". For existing offerings that are due for a subsequent security review, log a case in the Partner Portal. - Pay the annual listing fee. Refer to the Listing Fee page to determine if this fee applies to your offering.
Additionally, http://www.salesforce.com/partners/isv/program-models/ states :
"With our percentage net revenue model, free apps have no fees beyond the $300 charged for security review"
So it would seem that you have to pay USD300 for the Security Review, and nothing more.
Perhaps @metadaddy or @superfell could confirm this for you.