had doesn't make any sense in the sentence unless you say had become, has become, had/has been becoming but actually no need to make the sentence so complicated.
First in English, the type 'begin to do + clause' is not used very often, it's not like Chinese '我开始逐渐明白……(with a clause after the verb added). So you can just say 'I feel/felt/have felt that', besides there is an 'increasingly' in the latter sentence which means 'begin to', too.
Obviously we'll normally choose to say 'as I began to feel that this island was' or '... island became...' to keep the tense the same AMAP.
However you actually could say 'is' in your sentence if you are not taking an English exam. Small difference between 'is' and 'was', readers will understand you all the same.