Learn Icelandic: Við lánum stelpunni alltaf reglustikuna.

This is because of the verb lána (to lend). Like many verbs of giving or sending, it requires two objects. The person receiving the item (the indirect object) goes into the dative case, which is why we use stelpunni. The item being lent (the direct object) goes into the accusative case, giving us reglustikuna.

Both stelpa and reglustika are weak feminine nouns. Why do their endings look different here?

Because they are in different cases and have the definite article attached. For stelpa (girl) in the dative, the base form is stelpu, and adding the definite dative article makes it stelpunni. For reglustika (ruler) in the accusative, the base form is reglustiku, and adding the definite accusative article makes it reglustikuna.

Could I put alltaf right after the verb, like Við lánum alltaf stelpunni reglustikuna?

Yes, you can! In Icelandic, frequency adverbs like alltaf usually follow the verb. However, when you have a definite indirect object like stelpunni, it is very common and natural to place the adverb right after it, separating the two objects just like in this sentence.

If we replaced stelpunni with the pronoun for 'her', what would the sentence look like?