Alright, i've solved it! I'd like to share how it is done... I must say, programming world is new to me and hell it is very interesting :) And it is the first time I've used any kind of API... Here is a working example: http://codepen.io/everdimension/pen/LpfEH?editors=001

Explained:

So, first thing you gotta know is how to add markers. That can be easily found in maps API documentation. The marker is added like that:

var marker = new google.maps.Marker({ marker_properties });

Ok, so how do we add all the markers for the places you have? Well, you simply iterate through the places which have coordinates. First, let's create the places array:

var random_places = [

  ['Moscow1', 55.822083, 37.665453, 4],

  ['Moscow2', 55.604697, 37.642107, 4],

  ['Lisbon1', 38.749402, -9.120034, 4],

  ['Lisbon2', 38.708960, -9.169130, 4],

  ['NewYork1', 40.784513, -73.976630, 4],

  ['NewYork2', 40.707522, -74.037055, 4],

  ['Bondi Beach', -33.890542, 151.274856, 4],

  ['Coogee Beach', -33.923036, 151.259052, 5],

  ['Cronulla Beach', -34.028249, 151.157507, 3],

  ['Manly Beach', -33.80010128657071, 151.28747820854187, 2],

  ['Maroubra Beach', -33.950198, 151.259302, 1]

];

Ok, now let's iterate through these places and add a marker each time:

for (var i = 0; i < random_places.length; i++) {

    var beach = random_places[i];

    var myLatLng = new google.maps.LatLng(beach[1], beach[2]);

    var marker = new google.maps.Marker({

        position: myLatLng,

        map: map,

        title: beach[0],

    });

};

Ok, so this code just uses basic API functionality and should be no problem. But all the markers we've created exist on the map all the time, no matter if they are within the visible bounds or not. But we want the markers to appear only if they are within the part of the map we are looking at. Now that's exactly what my question was about. And here's how we can do it.

The key word is bounds. Turns out, with maps API we can make the following event listener:

google.maps.event.addListener(map, 'bounds_changed', function() { ... });

And the function will execute each time the bounds of the maps are changed! What we have to do is check if the markers fall within the current bounds and if they do, we'll create them. So here:

var place_markers = [];



google.maps.event.addListener(map, 'bounds_changed', function() {



    var bounds = map.getBounds();

    searchBox.setBounds(bounds); // not needed for our purpose, it adds bias to new     searches



    var NE = bounds.getNorthEast();

    var SW = bounds.getSouthWest();



    // Iterate through all places

    for (var i = 0; i < random_places.length; i++) {

            var place_arr = random_places[i];



            // Check if a place is within bounds - not best way, explained later

            if ( (NE.lat() > place_arr[1] && place_arr[1] > SW.lat()) &&

                    (NE.lng() > place_arr[2] && place_arr[2] > SW.lng()) ) {



                    var myLatLng = new google.maps.LatLng(place_arr[1], place_arr[2]);

                    var marker = new google.maps.Marker({

                            position: myLatLng,

                            map: map,

                            title: place_arr[0],

        });



        place_markers.push(marker);



    }

};



});

That's it! Now the markers only get created when they are within the visible part of the map!
You may have noticed that I had also created an empty place_markers object and then had pushed all created marked into it. Why? Because we need to do one more thing. We'd want to remove all the created markers if they fall outside of current bounds!
So each time the bounds are changed we would like for this code to execute:

// Remove out of bounds markers

for (var k = 0; k < place_markers.length; k++) {

  var one_marker = place_markers[k];

  if (!bounds.contains(one_marker.getPosition())) {

    one_marker.setMap(null);

  }

}

You can see that here I've used a built in bounds.contains() function to check if a created marker is within bounds. Same function can also be used when the markers are created, but I decided to leave the code like that to show the process of finding the correct solution.
The main thing is that the markers are now being removed when they fall out of bounds and get created when they are within!

One more thing I have to say. It's not the only way to accomplish the task I wanted. It can be done in many other ways. I have found a step-by-step explanation of an advanced way which uses PHP and MySQL:
https://developers.google.com/maps/articles/phpsqlsearch_v3

I hope this will be useful for someone who is, like me, new to google maps api.