Locking in stored procedures
My understanding of this is that, yes, under a transaction your SP will hold locks for the duration of the transaction. (Note there are lots of types of locks - SQL Server could row lock, table lock, page lock etc)

One SP being called simultaneously (with no other activity on your DB) causing deadlocks suggests one thing to me: the SP is not locking the same things in the same order on each call. Do you have IF blocks that perform actions on a table if a condition is met? You may wish to rewrite those to make the IF condition appear in the WHERE condition instead. This will ensure the SP locks the same resources in the same order each time.