Nala and Neela who were very powerful monkeys and mischievous in their childhood used to throw away objects in the water just for fun. when they threw away a certain sage in the water,they were cursed that nothing will be drowned in the water if it will be thrown by them.
They as the vanara supporters to Lord Rama were enough to build the bridge Rama-Setu.
But still why did Lord Rama pray to the Sea God?
I do not know the source of the story that was quoted about Nala and Neela in the question. As far as I understood, Valmiki's Srimad Ramayana does not contain this story.
Coming to the question of necessity of praying the Sea God, when Nala was very much available on Sri Rama's side, my answer is follows:
Here we have to understand 2 issues.
1) Construction of a massive bridge for a length of 100 Yojanas, i.e, 100 x 13 kms = 1,300 Kms ( As 1 Yojana = 13 Kms)
2) Permission of Sea God for the passage of Vanaras through sea.
I) Sri Rama started praying the Sea God on the advice of Vibhishana, for safe passage of the army.
उपायैर् अभिगच्चामो यथा नद नदी पतिम् || ६-१९-२९ तराम तरसा सर्वे ससैन्या वरुण आलयम् |
"In what manner shall we along with the army swiftly cross the sea, the lord of streams and rivers, and arrive at that strategy?"
एवम् उक्तस् तु धर्मज्ञः प्रत्युवाच विभीषणः || ६-१९-३० समुद्रम् राघवो राजा शरणम् गन्तुम् अर्हति |
Hearing their words, the right minded Vibhishana replied as follows: "It is apt if prince Rama seeks ocean as his refuge"
अबद्ध्वा सागरे सेतुम् घोरे अस्मिन् वरुण आलये || ६-१९-३९ लंका न आसादितुम् शक्या स इन्द्रैर् अपि सुर असुरैः |
"Without constructing a bridge across this fiery ocean, which is an abode of Lord Varuna, even the celestials and demons along with Indra cannot reach the city of Lanka."
एवम् उक्तः कुश आस्तीर्णे तीरे नद नदी पतेः | सम्विवेश तदा रामो वेद्याम् इव हुत अशनः || ६-१९-४२
Having been thus exhorted, Rama then sat on the shore of the ocean covered with blades of Kusha grass, as the God of Fire ascends the altar.
So in order to appease the Sea God, Sri Rama prayed to him.
Then the Sea God, told the way to cross him.
विधास्ये येन गन्तासि विषहिष्ये ह्यहम् तथा | न ग्राहा विधमिष्यन्ति यावत्सेना तरिष्यति || २-२२-२८ हरीणाम् तरणे राम करिष्यामि यथास्थलम् |
"O, Rama! I shall make it possible to see that you are able to cross over. I will arrange a place for the monkeys to cross me and bear with it. As far as the army crosses me, the crocodiles will not be aggressive to them."
II) Coming to 2nd part of the question, Sri Rama does not know that Nala, the son of Viswakarma, who is on is side, is also great architect as his father is.
It was the Sea God, who told to utilise the services of Nala.
अयम् सौम्य नलो नाम तनुजो विश्व कर्मणः | पित्रा दत्त वरः श्रीमान् प्रतिमो विश्व कर्मणः || २-२२-४४
"O, excellent man! This one, named Nala, a glorious person, is the son of Vishvakarma; who was given a boon by his father and is equal to Visvakarma."
एष सेतुम् महाउत्साहः करोतु मयि वानरः | तम् अहम् धारयिष्यामि तथा हि एष यथा पिता || २-२२-४५
"Let this greatly energetic monkey build a bridge across me. I can hold that bridge. He is just the same as his father."
The exact answer of the question - Why did Lord Rama pray to the Sea God? And source of the story that was quoted about Nala and Neela are also provided in Sundar-Kanda of Shree Tulsidas Ramacharitamanas (PDF Download Link).
Similar to Valmiki Ramayana, Ramcharitamanas also tells us that Lord Rama prayed to the Sea God on the advice of Vibhishana in order to construct a bridge over the sea for the passage of Vanaras. So Lord Rama in order to take permission to build a bridge over sea , prayed to Sea God.
Choupai -:
सुनत बिहसि बोले रघुबीरा | एसेहिं करब धरहु मन धीरा |
अस कहि प्रभु अनुजहि समुजाई | सिन्धु समीप गए रघुराई ||३||
प्रथम प्रनाम कीन्ह सिरु नाई | बैठै पुनि तट दर्भ डसाई |
जबहिं बिभीषन प्रभु पाहिं आए | पाछे रावन दूत पठाए || ४|| (Dupai – 50)sunata bihasi bole raghubira, aisehin karaba dharahu mana dheera
asa kahi prabhu anujahi samujhaee, sindhu samipa gae raghuraee 3.
prathama pranåma kihna siru naae, baithai puni tat darbha ˛dasaee
jabahiÚ bibhishana prabhu pahin aaye, paache ravana duta pathaye .4Reassuring His younger brother (Laxmana) with these words the Lord of the Raghus went to the seashore. First of all He bowed His head and greeted the ocean and then, spreading some Kusha grass on the shore, took His seat thereon. As soon as Vibhishana proceeded towards the Lord, Ravana sent spies after him.
राम तेज बल बुधि बिपुलाई | सेष सहत सत सकहिं न गाई ||
सक सर एक सोषि सत सागर | तव भ्राताहि पून्छेउ नय नागर || १||
तासु बचन सुनि सागर पाहीं | मागत पन्थ कृपा मन माहिं ||
सुनत बचन बिहसा दससीसा | जौ असि मति सहाय कृत किसा ||२||
सहज भीरु कर बचन द्रुढाई | सागर सन ठानी माचलाई |
मृढ मृषा का करिसी बडाई | रिपु बल बुद्धि थाह मैं पाई || ३|| - (Dupai -55)rama teja bala budhi bipulai seshaa sahasa sata sakahin na gaai .
saka sara eka soshii sata sagara, tava bhratahi pµu¡ cheu naya nagar.
tasu bachana suni sagara pahin, magata pantha krupa mana mahin
sunata bacana bihasa dasasisa , jau asi mati sahaya kruta kisa
sahaja bhiru kara bacana dhrudai , sagara sana thaani machalaee
mrudha mrusha ka karasi badaee | ripu bala buddhi thaha mai paaee.A hundred thousand sesas would fail to describe the greatness of Shree Rama's valour, strength and intelligence. With a single shaft He could dry up a hundred seas; yet, being a master of propriety, He consulted your brother Vibhishana and in accordance with his suggestion He is asking passage of the ocean with a heart full of compassion.
